글 읽기 - c언어 시간초과

hhyem 2년 전 0

계속 시간초과가 뜨는데 왜 그러는지 모르겠어요.

알려주세요..

#include <stdio.h>
int main() {
	
	int min = 0, max = 0, tmp = 0;
	scanf("%d %d", &min, &max);

	for (int i = min; i <= max; i++) {
		for (int j = 2; j < i; j++) { 
			if (i % j == 0) {
				tmp = 1;
			}
		}
		if (!tmp)
			printf("%d\n", i);
		tmp = 0;
	}
}

euphoric_n 2년 전 1

문제 조건에 의하면 M, N은 1이상 100만 이하입니다.

최악의 경우인 M=1, N=100만의 입력을 가정했을 때,

1 ~ 100만의 i에 대해 0~999999번 반복하면서 나누어 떨어지는지 확인하게 됩니다.

이는 대략 100만^2 = 1조번에 해당하는 연산 횟수입니다. 당연히 시간초과가 발생하게 됩니다.

이 문제를 풀기 위해서는 "에라토스테네스의 체" 알고리즘이 필요합니다.

어렵지 않은 소수 판정 알고리즘이므로 검색을 통해 공부해보시는 것을 권해드립니다.

o98123 2년 전 1

끝까지 다 나눠볼 필요는 없고요 sqrt(i)보다 작은 소수들로만 나누어보면되요

hhyem 2년 전 0

감사합니다!! 덕분에 해결했어요

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

문제

문제

출처

ICPC

c언어 시간초과

hhyem 2년 전 0

euphoric_n 2년 전 1

o98123 2년 전 1

hhyem 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말