글 읽기 - 시간초과 원인을 알고 싶습니다.

gkdud0701 4년 전 0

계속 시간초과가 나는데

Eratos에서 문제인건지 solve에서 문제인건지 알 수가 없네요,,,,, 주륵,, 도와주세요!!!

#include <stdio.h>

#define ERROR "Goldbach's conjecture is wrong.\n"

bool prime[1000002];

void Eratos(int n)
{
	if (n <= 1) return;

	for (int i = 0; i < n; i++) {
		prime[i] = true;
	}

	for (int i = 2; i * i <= n; i++)
	{
		if (prime[i]) {
			for (int j = i * 2; j <= n; j += i) {
				prime[j] = false;
			}
		}
	}
}

void solve(int _n) {
	int maxValue = -1;
	int temp_a, temp_b;
	for (int i = 3; i <= _n/2; i += 2) {
		if (prime[i] && prime[_n - i]) {
			if (maxValue < _n - i - i) {
				maxValue = _n - i - i;
				temp_a = i;
				temp_b = _n - i;
			}
		}
	}
	if (maxValue==-1) {
		printf(ERROR);
	}
	else {
		printf("%d = %d + %d\n", _n, temp_a, temp_b);
	}
}

int main() {
	int n;
	Eratos(1000000);
	while (1) {
		scanf("%d", &n);
		if (n == 0) {
			return 0;
		}
		solve(n);
	}
	return 0;
}

djm03178 4년 전 1

solve를 하던 도중 답이 하나 발견되었으면 곧바로 출력하면 됩니다. 가장 먼저 발견된 것이 무조건 둘의 차이가 가장 큰 것일 텐데, 그 이후까지 더 뒤질 필요가 있을까요?

gkdud0701 4년 전 0

헉 감사합니다!! 사랑해요ㅠㅠ

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

문제

문제

출처

ICPC

시간초과 원인을 알고 싶습니다.

gkdud0701 4년 전 0

djm03178 4년 전 1

gkdud0701 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말