글 읽기 - c언어 시간초과

rlaalswn1584 3년 전 0

시간초과가 뜨는 이유를 영 모르겠습니다..

답답하고 궁금해서 질문남겨봅니다!

#include <stdio.h>
#include <math.h>

int main(void)
{
	int a;
	int cnt = 0;
	for(;;)
	{
		
		scanf("%d", &a);
		if (a == 0)
			break;
		else if (a == 1 || a == 2) printf("%d\n", 1);
		else
		{
			for (int i = a + 1; i <= 2 * a; i++)
			{
				for (int j = 2; j <= sqrt(i); j++)
				{
					if (i % j == 0)
					{
						++cnt;
						break;
					}
				}
			}
			printf("%d\n", (a - cnt));
			cnt = 0;
		}
	}
	return 0;
}

BaaaaaaaaaaarkingDog 3년 전 1

123456

...

123456

이런 입력이 들어온다면 시간 초과가 날 수 있습니다.

매번 들어온 a에 대해 a+1 ~ 2a에서 소수의 개수를 세면 중복된 연산이 생기니까 그 대신 미리 1부터 123456*2 까지의 수들에 대해 소수인지 아닌지 여부를 다 계산한 후에 prefix sum을 이용해 처리를 하면 시간을 줄일 수 있습니다.

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

문제

문제

출처

ICPC

c언어 시간초과

rlaalswn1584 3년 전 0

BaaaaaaaaaaarkingDog 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말