글 읽기 - 시간초과가 왜 나느 걸까요....

xowns9418 7년 전 0

먼저 데이터의 MAX 값인 1000000까지 에라토스테네스의 체로 소수를 모두 구한뒤

앞에서부터 합이 N이 되는 쌍을 찾아서 찾으면 바로 출력되게 하였는데 뭐가 문제일까요??!

#include<iostream>
using namespace std;
#define MAX_SIZE 1000000

int arr[1000000] = { 0, };
int N;
bool flag;
int main(void) {
	ios::sync_with_stdio(false);
	arr[0] = 1;
	arr[1] = 1;
	
	for (int i = 2; i*i < MAX_SIZE; i++) {//에라토스테네스의 체
		for (int j = i*i; j < MAX_SIZE; j = j + i) {
			if (arr[j] == 0)
				arr[j] = 1;
 		}
	}
	while (1) {
		cin >> N;
		flag = false;
		if (N == 0)
			break;
		else {
			for (int i = 3; i*2 <= N; i+=2) {
				if (arr[i] == 0 && arr[N - i] == 0) {
					cout << N << " = " << i << " + " << N - i << '\n';
					flag = true;
					break;
				}
			}
			if (!flag)
				cout << "Goldbach's conjecture is wrong." << '\n';
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 왜 나느 걸까요....

xowns9418 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말