[6588번] 골드바흐의 추측

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 에라토스테네스의 체

에라토스테네스의 체를 통해 소수를 형성하고, 그 홀수인 소수를 이용하여 두수의 합이 짝수가 되는지 확인하는 방식은

짝수가 n이라면 홀수는 i, n - i가 된다.

따라서 아래 코드처럼 

            if (!isNotPrime[i] && !isNotPrime[n - i])

            {

                printf("%d = %d + %d\n", n, i, n - i);

                chk = true;

                break;

            }

이 방식을 이용하면 답을 구할 수 있다.

소스 코드 : 

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 40 41 42 43 44 45 46

#include <iostream> #include <cstdio> #include <algorithm> #include <vector>   #define SIZE 1000003   using namespace std;   int isNotPrime[SIZE];   void eratosthenes() {     for (int i = 2; i*i < SIZE; i++)         if (!isNotPrime[i])             for (int j = i*i; j < SIZE; j += i)                 isNotPrime[j] = 1;     isNotPrime[1] = 1; }   int main() {     eratosthenes();          int n;     while (1)     {         scanf("%d", &n);         if (n == 0)             break;           bool chk = false;         for (int i = 3; i <= n; i += 2)             if (!isNotPrime[i] && !isNotPrime[n - i])             {                 printf("%d = %d + %d\n", n, i, n - i);                 chk = true;                 break;             }         if (!chk)             printf("Goldbach's conjecture is wrong.\n");     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus