글 읽기 - 시간초과인 이유는 무엇인가? (3점

seojoon94 6년 전 0

여기서 왜 시간초과가 뜨는 지 모르겠네요ㅠㅠ

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

int count = 0;
unsigned long long int min, max;

void getMinMax() {
	scanf("%u %u", &min, &max);
}

void NumCount() {
	int flag;
	unsigned long long int i, j, sqr;
	for (i = min; i <= max; i++) {
		flag = 1;
		sqr = (unsigned long long)sqrt(i);
		for (j = 2; j <= sqr; j++) {
			if (i % (j*j) == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1)
			count++;
	}
}

int main(void) {
	getMinMax();
	NumCount();
	printf("%d\n", count);
}

rdd6584 6년 전 1

sqr(i) * (max - min)

최악의 경우 대략 연산수가 100억정도가 넘어갈 것 같아요. 정확히 계산해보지는 않았는데.

소수를 다른 방법으로 구해보세요.

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

문제

문제

출처

ICPC

시간초과인 이유는 무엇인가? (3점

seojoon94 6년 전 0

rdd6584 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말