BOJ::6588 골드바흐의 추측

https://www.acmicpc.net/problem/6588


1. 에라토스 테네스의 체를 이요하여 소수를 판별한다.


2. 3~1000000 사이 홀수 소수를 벡터 v에 넣는다.


3. x가 두 홀수 소수의 합으로 표현이 가능한지 찾는다.


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
35
36
37
38
39
#include <iostream>
#include <vector>
#define P pair<int,int>
using namespace std;
 
int primes[1000001];
vector<int> v;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    //에라토스테네스의 체
    for (int i = 2; i <= 1000000; i++) {
        for (int j = 2; i*j <= 1000000; j++) {
            if (primes[i*j])continue;
            primes[i*j] = true;
        }
    }
    //3이상 소수 벡터에 푸쉬
    for (int i = 3; i <= 1000000; i++) {
        if (!primes[i])v.push_back(i);
    }
 
    int x;
    while (true) {
        cin >> x;
        //종료조건
        if (x == 0)break;
 
        //두 소수의 합으로 표현 가능한지 확인
        for (int i = 0; i < v.size(); i++) {
            if (!primes[x - v[i]]) {
                cout << x << " = " << v[i] << " + " << x - v[i] << "\n";
                break;
            }
        }
    }
 
}
cs

 


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

7562 나이트의 이동  (0) 2018.01.06
6603 로또  (0) 2018.01.06
5014 스타트링크  (0) 2018.01.06
3187 양치기 꿍  (0) 2018.01.06
2668 숫자고르기  (0) 2018.01.06

+ Recent posts

티스토리툴바