글 읽기 - C언어 4948번 가르쳐주시면 감사하겠습니다.

skytower144 3년 전 0

에라토스테네스의 체를 이해하는데 개인적으로 너무 어려웠습니다..

이해가 겨우 가는가 싶었는데 더군다나 구현은 더욱 어렵게 느껴집니다;

입력을 넣어봤는데 답은 예제대로 나오는 것 같습니다. 막상 제출을 하면 20%정도에서 틀렸다고 나옵니다.

어느 부분을 고쳐야하는지 알려주시면 감사하겠습니다.

#include<stdio.h>
#include<math.h>
int main(void)
{
	int N; int ct=0;

	START:
		scanf("%d", &N);
		while(N !=0)
		{
			int num[246913] = {1,1,0, };
			ct = 0;
			for(int k=2; k<=2*N; k++)
			{
				if(num[k] == 1)
					continue;
				if(pow(k,2)>=2*N)
					break;
				for(int j=k*k; j<=2*N; j = j+k)
					num[j] = 1;
			}
			for(int i=N+1; i<= 2*N; i++)
			{
				if(num[i] == 0)
				{
					ct++;
				}
					
			}
			printf("%d\n",ct);
			goto START;
		}
	
	return 0;
}

skytower144 3년 전 0

if(pow(k,2)>=2*N) 를 if(pow(k,2)>2*N) 로 바꾸었더니 바로 해결되었습니다..

그래도 이해가 아직 잘 안갑니다..

>=로 하면 틀리는 이유나 반례를 알려주시면 감사하겠습니다.

shoon125 3년 전 1

2를 입력받으면 루프를 돌지 않고 바로 빠져나오기 때문에 출력값이 제대로 나오지 않는것 같습니다.

skytower144 3년 전 0

입력값이 2일 때 루프를 돌지 않고 바로 빠져나오는 바람에 num[4] 값 설정을 생략해버리는군요! 이해가 바로 갔습니다.. 감사합니다.

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

문제

문제

출처

ICPC

C언어 4948번 가르쳐주시면 감사하겠습니다.

skytower144 3년 전 0

skytower144 3년 전 0

shoon125 3년 전 1

skytower144 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말