글 읽기 - 시간초과뜨는데 어디서 시간을 줄여야할까요ㅠㅠ

dlehdgns7 3년 전 0

while문 안에 이중 for문에서 시간을 줄여야할듯 한데 고수님들 도와주세요 ㅠㅠ

#include <iostream>
#include <cmath>
using namespace std;
int arr[1000001] = { 1, 1, 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	for (int i = 2; i <= sqrt(1000000); i++) {
		for (int k = i * i; k <= 1000000; k += i) {
			arr[k] = 1;
		}
	}
	int a, b;
	while (true) {
		a = 0, b = 0;
		cin >> n;
		if (n == 0)
			break;
		for (int i = n; i >= 2; i--) {
			if (arr[i] == 0) {
				for (int k = 2; k <= n; k++) {
					if (arr[k] == 0) {
						if (i + k == n) {
							a = i;
							b = k;
							break;
						}
					}
				}
			}
			if (a + b == n)
				break;
		}
		if (a == 0 && b == 0)
			cout << "Goldbach's conjecture is wrong." << '\n';
		else
			cout << n << " = " << b << " + " << a << '\n';
	}
	return 0;
}

kjw0914 3년 전 1

합이 n인 두 소수를 찾을 때 모든 소수 쌍을 시도하면 안 됩니다. 시간 복잡도에 대해 배우면 이 방법이 O(n^2)의 시간이 걸린다는 것을 알 수 있습니다. 소수 p를 선택하면 나머지 하나는 n-p여야 한다는 점을 활용해 보세요.

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

문제

문제

출처

ICPC

시간초과뜨는데 어디서 시간을 줄여야할까요ㅠㅠ

dlehdgns7 3년 전 0

kjw0914 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말