글 읽기 - [골드바흐추측] 시간초과... 잠이 안옵니다.

donghp 4년 전 0

어디가 틀린 부분인가요 ㅜㅜ

3번에 걸쳐서 수정한 코드인데 이유를 모르겠네요 ㅠㅠ.

미리 감사드립니다.

#include <iostream>
#include <vector>

using namespace std;
/*
	가설: 4 보다 큰 모든 짝수는 두 홀수소수의 합으로 나타낼 수 있다.
*/
int n;
const int Max = 1000000;
bool arr[Max+1];

void eratos() {
	for (int i = 2; i <= Max; i++) 
		arr[i] = true;

	for (int i = 2; i*i <= Max; i++) {
		if(arr[i]) // 소수이면
			for (int j = i*i; j <= Max; j += i) { 
				arr[j] = false; // 배수는 모두 소수가 아니다.
		}
	}
}

int main() {
	eratos();
	while (1) {
		cin >> n;
		if (n == 0) return 0;

		int o1 = 0, o2 = 0; 
		for (o1 = 3; o1 <= n - 1; o1++) { 
			if (arr[o1]) { //0이 아니고 : 소수이며
				o2 = n - o1; // o1 + o2 = n을 만족하는 o2가 있을때,
				if (arr[o2]) { //o2도 소수이면
					cout << n << " = " << o1 << " + " << o2; 
					break;
				}
			}
		}
        if(o1 == n){
			cout << "Goldbach's conjecture is wrong.";
        }
	}
	return 0;
}

kyo20111 4년 전 1

cin cout이 매우 느립니다. 입출력 방식을 바꾸어주고 개행문자를 추가해주었더니 맞았습니다.

djm03178 4년 전 3

https://www.acmicpc.net/proble...

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

문제

문제

출처

ICPC

[골드바흐추측] 시간초과... 잠이 안옵니다.

donghp 4년 전 0

kyo20111 4년 전 1

djm03178 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말