[백준] 6588번: 골드바흐의 추측

Kim Yuhyeon·2022년 4월 26일

cpp 백준 알고리즘

알고리즘 + 자료구조

목록 보기

45/161

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

문제

알고리즘 접근 방법

소수 판별

에라토스테네스의 체 를 이용하여 소수 판별
한 번만 해놓고 계속 쓴다!!!

이 때 i<=sqrt(1000000)까지만 돌려도 됨

테스트 케이스

n을 입력 받고 (이 전에 n 초기화 해줄 것)

i<=n/2 까지만 계산하면서 소수끼리의 합을 구해줄 것

제일 작은 해 하나 고르면 바로 나와도 됨.

주의할 점

25%~33%에서 시간초과 뜬다면
cin, cout 대신 scanf, printf 이용해볼 것
난 바꾸니까 바로 통과했다 .. ! ㅠㅇㅠ

풀이

#include <iostream>
#include <stdio.h>
#include <cmath>
#define SIZE 1000001

using namespace std;

// 에라토스테네스의 체 초기화 
bool arr[SIZE] = {false};

int main(){ 

    int n = -1;
    arr[0] = true;
    arr[1] = true;


    // 소수 판별
    for(int i=2; i<=sqrt(SIZE); i++){
        if (arr[i] == true)
            continue;
        for(int j=i+i; j<=SIZE; j+=i){
            if(arr[j] == false)
                arr[j] = true;
        }
    }

    while(true){
        scanf("%d", &n);

        if (n == 0)
            return 0;
        else{
            bool find = false;
            int I;
            for(int i=2; i<=n/2; i++){
                if (!arr[i] && !arr[n-i]){
                    I = i;
                    find = true;
                    break;
                }
            }               
            if (find)
                printf("%d = %d + %d\n", n, I, n-I);
            else
                printf("Goldbach's conjecture is wrong.");
        }
    }
    return 0;
}