반응형

www.acmicpc.net/problem/6588

 

6588번: 골드바흐의 추측

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
using namespace std;
bool not_prime[1000001];
vector<int> v;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // 소수가 아닌 숫자 찾기
    not_prime[1] = 1;
    for (int i = 2;i <= 1000000;i++) {
        if (not_prime[i]) continue;
        for (int j = 2;i * j <= 1000000;j++) 
            not_prime[i * j] = 1;
    }
    // 모든 소수를 벡터에 저장
    for (int i = 3;i <= 1000000;i++) {
        if (!not_prime[i])
            v.push_back(i);
    }
    int n;
    cin >> n;
    while (n != 0) {
        for (int i : v) {
            if (!not_prime[n - i]) {
                cout << n << " = " << i << " + " << n - i << '\n';
                break;
 
            }
        }
        cin >> n;
    }
    
}
cs
반응형

+ Recent posts

티스토리툴바