JArchive 프로그래밍 일기

문제

골드바흐의 추측 백준 6588번

리뷰

두 홀수 소수의 합으로 N을 나타낼 수 있는지 검사하는 문제다.

짝수 정수 N의 범위 (6 ≤ N ≤ 1000000)

에라토스테네스의 체 문제 소수 구하기 백준 1929번를 풀어보고 나니까 막막하진 않았다.

문제의 풀이과정은 아래와 같다.

1. 에라토스테네스의 체로 백만 까지의 소수를 모두 구한다. (Eratos 함수 )
2. Prime 벡터에 홀수 소수들만 저장한다. (Eratos 함수 )
3. Prime 벡터를 순회하면서 N-Prime[i] 가 Prime 에 있는지 검사한다. ( Gold 함수 )

Gold 함수 case1

2중 for문으로 작성한 형태

bool Gold(int n){ // Prime 을 순회하면서 n을 a+b로 나타낼수 있는지 확인  

    for(int i = 0; Prime[i] < n; i++){ // a와 b는 n보다는 작을테니 n 직전까지만 탐색

        int target = n - Prime[i]; // n = a + b 가 되어야 하니까 b를 찾아본다. 

        for(int j = i; Prime[j] < n; j++){
            if(target == Prime[j]){
                printf("%d = %d + %d\n", n, Prime[i], Prime[j]);
                return true;
            }
        }
    }

    return false;
}

Gold 함수 case2

for문을 1개로 쓴 형태

bool Gold(int n){

    for(int i = 0; Prime[i] < n; i++){ // a와 b는 n보다는 작을테니 n 직전까지만 탐색

        if(n-Prime[i] == A[n-Prime[i]]){  // n-Prime[i] 값이 소수인지 확인한다 
            printf("%d = %d + %d\n", n, Prime[i], n-Prime[i]);
            return true;
        }
    }

    return false;
}

질문게시판에서 도움 받은 글

Gold 함수의 내부 for문에서 j를 i+1로 초기화 하고 시작했다가 틀렸다.

입력으로 6을 넣었을 때, 6 = 3 + 3 으로 표현할 수 있다. 따라서 내부 for문은 j = i로 초기화 해야 한다.

맞은 코드1

#include <iostream> 
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;

int A[1000001];  // 모든 소수
vector<int> Prime;  // 홀수 소수 

void Eratos(void){ // 백만 까지의 소수를 모두 구한다. 

    A[0] = A[1] = 1; // 0과 1은 소수가 아니다.  

    for(int i = 2; i<= MAX; i++){
        A[i] = i; // A배열 값을 '자기 자신'으로 저장한다.  
    }

    for(int i = 2; i*i <= MAX; i++){

        if(A[i] == i){

            for(int j = i*i; j <= MAX; j+=i){
                A[j] = i;  // 소수의 배수들을 지운다  
            } 
        }
    }

    // 홀수인 소수만 Prime에 저장  
    for(int i = 3; i<= MAX; i++){
        if(A[i] == i) Prime.push_back(A[i]);        
    }
}

bool Gold(int n){ // Prime 을 순회하면서 n을 a+b로 나타낼수 있는지 확인  

    for(int i = 0; Prime[i] < n; i++){

        int target = n - Prime[i];

        for(int j = i; Prime[j] < n; j++){
            if(target == Prime[j]){
                printf("%d = %d + %d\n", n, Prime[i], Prime[j]);
                return true;
            }
        }
    }

    return false;
}

int main(void){

     Eratos();

     while(1){
         int n = 0;
         scanf("%d", &n);

        if(n == 0) break;

         if(!Gold(n)) cout << "Goldbach's conjecture is wrong.\n"<<'\n';
    }

    return 0;    
} 

맞은 코드2

#include <iostream> 
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;

int A[1000001];  // 모든 소수
vector<int> Prime;  // 홀수 소수 

void Eratos(void){

    A[0] = A[1] = 1; // 0과 1은 소수가 아니다  

    for(int i = 2; i<= MAX; i++){
        A[i] = i; // 자기 자신을 저장시킨다  
    }

    for(int i = 2; i*i <= MAX; i++){

        if(A[i] == i){

            for(int j = i*i; j <= MAX; j+=i){  // 소수의 배수들을 지운다  
                A[j] = i; 
            } 
        }
    }

    for(int i = 3; i<= MAX; i++){ // 홀수인 소수만 Prime에 저장  
        if(A[i] == i) Prime.push_back(A[i]);        
    }

}

bool Gold(int n){

    // P 를 순회하면서 n을 a+b로 나타낼수 있는지 확인  
    for(int i = 0; Prime[i] < n; i++){

        if(n-Prime[i] == A[n-Prime[i]]){
            printf("%d = %d + %d\n", n, Prime[i], n-Prime[i]);
            return true;
        }
    }

    return false;
}

int main(void){

     Eratos();

     while(1){
         int n = 0;
         scanf("%d", &n);

        if(n == 0) break;

         if(!Gold(n)) cout << "Goldbach's conjecture is wrong.\n"<<'\n';
    }

    return 0;    
}