글 읽기 - 시간초과 극복 가능한가요?

dpwns1234 4년 전 0

1 부터 1000000까지 엄청나게 많은 소수가 있는데 그걸 시간초과없이 출력하는게 가능합니까?? 소수만 찾은다음 for문으로 입력된 값만 출력해도 시간초과 뜰 것 같은데...ㅜㅜㅜ

#include <stdio.h>

int main()
{
	int a = 0, b, m, n;
	scanf("%d %d", &m, &n);
	for (; m <= n; m++)
	{
		b = 0;
		for (int i = 1; i <= m; i++)
		{
			if (m % i == 0 && m != 1)
				b++;
		}
		if (b == 2)
			printf("%d", m);

		if (b == 2 && m != n)
			printf("\n");
	}
}

djm03178 4년 전 0

질문 게시판의 다른 질문들을 보고 아 저렇게도 할 수 있구나! 하는 걸 꺠달아보세요.

surung9898 4년 전 0

소수 판정에 있어서, 어떤 자연수 n을 판정하는 기준으로 보통 'n이 2부터 sqrt(n)까지의 수 중 하나로 나누어 떨어지는가'를 보통 채택합니다. 예시로, 32가 소수인지를 판정할 때에는 32를 2부터 5까지만 나누어 볾으로써 소수를 판정할 수 있습니다.

간략하게 설명드리자면, 32의 약수는 각각 1 2 4 8 16 32이므로, 32를 4를 나누어 보는 것과 8을 나누어 보는 것에는 차이를 가지지 않는다는 것입니다.

결과적으로, 어떤 수 n을 판정하기 위해서, 반복문을 2부터 sqrt(n)까지만 돌면서 나누어떨어지는 수가 나올 시 바로 반복문을 종료하시면 시간을 줄일 수 있을 것입니다.

atomzeno 4년 전 0

위의 방법도 있고

에라토스테네스의 체를 사용해도 됩니다

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

문제

문제

출처

ICPC

시간초과 극복 가능한가요?

dpwns1234 4년 전 0

djm03178 4년 전 0

surung9898 4년 전 0

atomzeno 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말