글 읽기 - 반례가 어떤게 있을지요?

cardbt 7년 전 0

안녕하십니까?

문제는 아주 단순하게 풀었습니다.

우선 10^6 이하의 수중에 소수를 먼저 구하고, 주어진 수를 소수들로 분해가 되는지 확인해서, 분해가 되면 NO, 아니면 YES로 했습니다.

문제를 잘못 이해한게 아니라면 딱히 반례가 없어보이는데, 제출하면 틀립니다로 나오네요.

어떤 반례가 있을까요?

#define TRUE 'o'
#define FALSE 'x'

main()
{
	char *isPrime;
	int i, j, k, pIndex;
	int Prime[100000];

	isPrime = (char *)malloc(1000001);
	memset(isPrime, TRUE, 1000001);
	pIndex = 0;

	for (i = 2; i <= 1000000; i++)
	{
		if (isPrime[i] == TRUE) Prime[pIndex++] = i;
		for (j = i*2; j <= 1000000; j +=i) isPrime[j] = FALSE;
	}

	for (scanf("%d", &i); i > 0; i--)
	{
		scanf("%d", &k);
		for (j = 0; j < pIndex; j++)
		{
			if (k % Prime[j] == 0) break;
		}

		if (j == pIndex) puts("YES");
		else puts("NO");
	}
}

sgchoi5 7년 전 0

입력이 int 형의 범위를 벗어나서 long long int 를 써야 할 듯 하네요.

cardbt 7년 전 0

아.. 멍청하네요 진짜 ㅋㅋㅋ

입력값이 엄청 큰수인데...

감사합니다

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

문제

문제

출처

ICPC

반례가 어떤게 있을지요?

cardbt 7년 전 0

sgchoi5 7년 전 0

cardbt 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말