글 읽기 - 시간초과가 되는이유..?

jungby1 5년 전 0

에라토스테네스의 체 이용했구요, 최대한 출력시간도 줄여서 제 visual studio에는 바로바로 뜨는데.....

1부터 1000000까지 해도 1초도 안되서 바로 출력이 되거든요?? 그런데 시간초과가 나오는 이유가 뭘까요;;;

설마 모든 소수를 출력하는데 2초라는 말이라면 애초에 소수개수가 7만개가 넘는데 그게 가능한가요..

고수님들의 조언이 필요한 시점입니다ㅠㅠㅠ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int ari(int a, int n, int b[]);

int main() {

	int m, n;
	int *num;
	num = (int*)calloc(1000001, sizeof(int));
	int i;
	scanf("%d%d", &m, &n);
	num[1] = 0;
	for (i = 2; i <= n; i++) {
	
		if (num[i] == 0) {
			ari(i, n, num);
			if (i >= m) {
				printf("%d\n", i);
			}
		}
	}
	free(num);
	return 0;
}

int ari(int a, int n, int b[]) {
	int i;
	for (i = a+1; i <= n; i++) {
		if (b[i] == 0) {
			if (i % a == 0) {
				b[i] = 1;
			}
		}
	}

	return 0;
}

minjun623 5년 전 0

int ari(int a, int n, int b[])의 for문을 수정 하시면 될 것 같네요.

jungby1 5년 전 0

정확히 for문이 어떻게 틀린건지 알려주실 수 있나요?ㅠㅠ

minjun623 5년 전 0

틀렸다고 하기 보다 같은 O(N)이여도 다른 시간 효율을 가질 수 있어요. 한번 생각해보세요

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

문제

문제

출처

ICPC

시간초과가 되는이유..?

jungby1 5년 전 0

minjun623 5년 전 0

jungby1 5년 전 0

minjun623 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말