글 읽기 - [9421/소수상근수] 50%에서 틀렸다고 뜹니다.

ychooni 7년 전 0

에라토스테네스의 체 기록해두고

소수인 것들을 벡터 p에 저장하고

그것들만 소수 상근수인지 검사를 하는 식으로 진행하였습니다.

검사는 중복되는 수가 발생하면 상근수가 아니도록 하였는데요,

제가 무엇을 생각하지 못하고 있는 걸까요? ㅜㅜ

#include <cstdio>
#include <vector>
using namespace std;

#define MAX_N	1000001

bool notPrime[MAX_N], notAns[MAX_N];
vector<int> p;


void setErasto(int n)
{
	int i, j;
	for(i=2; i*i<MAX_N; i++) {
		if(!notPrime[i]) {
			p.push_back(i);
			for(j=i*i; j<MAX_N; j+=i)
				notPrime[j] = 1;
		}
	}
}

bool isAns(int n)
{
	bool check[MAX_N]={0};
	vector<int> x;

	while(n != 1) {
		int sum=0;
		check[n] = 1;
		x.push_back(n);
		while(n) {
			sum += (n%10)*(n%10);
			n/=10;
		}
		n = sum;
		if(notAns[n] || check[n]) {
			for(int i=0; i<x.size(); i++) 
				notAns[x[i]] = 1;
			return 0;
		}
	}
	return 1;
}

int main()
{
	int i, n;
	scanf("%d", &n);
	setErasto(n);

	for(i=1; i<p.size() && p[i]<=n; i++) {
		if(isAns(p[i]))
			printf("%d\n", p[i]);
	}
}

sait2000 7년 전 1

디버깅은 아직 안 했지만 1009가 소수상근수인데 1009를 입력으로 넣으면 1009가 안 나오네요.

sait2000 7년 전 1

i*i<MAX_N이라서 1000 보다 큰 소수가 아예 고려되지도 않고 있네요;;

void setErasto(int n)
{
	int i, j;
	for(i=2; i*i<MAX_N; i++) {
		if(!notPrime[i]) {
			p.push_back(i);
			for(j=i*i; j<MAX_N; j+=i)
				notPrime[j] = 1;
		}
	}
}

ychooni 7년 전 0

답변 감사드립니다..!!

하지만,,,, 이번엔 시간초과의 늪에 빠지게 되었네요..ㅜㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[9421/소수상근수] 50%에서 틀렸다고 뜹니다.

ychooni 7년 전 0

sait2000 7년 전 1

sait2000 7년 전 1

ychooni 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말