글 읽기 - 시간초과

jeonhoonjin 5년 전 0

어떻게해결합니까..

시간초과가 계속뜹니다 10만개 기준 1초쯤뜨는거같은데

더욱줄일방법있습니까?

#include <stdio.h>
#include <math.h>
int main()
{
	int n, i, j,cnt=0,k;
	while (1)
	{
		scanf("%d", &n);
		if (n == 0) break;
		for (i = n + 1; i <= 2 * n; i++)
		{
			k = i;
			for (j = 2; j <= sqrt(i); j++)
			{
				if (i % j == 0)
				{
					k = 0;
				}
			}
			if ((k != 0 && k!=1) || k==2)
			{
				cnt++;
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
	}
}

djm03178 5년 전 1

테스트 케이스마다 일일이 cnt를 구하지 말고, "n까지의 소수의 수"를 어딘가에 저장해두어 보세요.

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

문제

문제

출처

ICPC

시간초과

jeonhoonjin 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말