글 읽기 - 시간초과에서 소수 배열을 넣는 반복문에서

lkc263 4년 전 0

시간초과가 계속나오네요. 하하..

while문안에 있는 for문두개가 문제점인 것 같은데 맞는걸까요?

for (int i = 2; i <= num; i++) {
if (check[i] == false && (i % 2)) {
prime[pn++] = i;
}
for (int j = i * 2; j <= num; j += i) {
check[j] = true;
}
}

// 골드바흐의 추측
// 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
// 위의 문장에 3을 더하면 5보다 큰 모든 홀수는 세 소수의 합으로 표현가능



#include<iostream>
using std::cin;
using std::cout;

#define MAX_LEN 1000000
bool finishLine;
bool check[MAX_LEN + 1];     // 기본값 false
int prime[MAX_LEN];

int main() {
	int num;
	int pn = 0;
	int a, b;  // 위치


	while (1) {
		cin >> num;

		if (num == NULL) {
			break;
		}

		for (int i = 2; i <= num; i++) {
			if (check[i] == false && (i % 2)) {
				prime[pn++] = i;
			}
			for (int j = i * 2; j <= num; j += i) {
				check[j] = true;
			}
		}

		for (int i = 0; i < pn; i++) {
			for (int j = i; j < pn; j++) {
				if (prime[i] + prime[j] == num) {
					a = i;
					b = j;

					finishLine = true;
					break;
				}
			}

			if (finishLine == true) {
				break;
			}
		}


		if (pn == 0) {
			cout << "Goldbach's conjecture is wrong.";
		}
		else {
			cout << num << " = " << prime[a] << " + " << prime[b];
		}

		cout << '\n';
		pn = 0;
		finishLine = false;
	}


	return 0;
}

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

문제

문제

출처

ICPC

시간초과에서 소수 배열을 넣는 반복문에서

lkc263 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말