코드플러스 기초 - 6588 (C++)

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

6588번: 골드바흐의 추측

 

문제 해결

1.기초 문제들에서 게속 쓰이는 에라스토테네스 체로 소수들의 배열을 미리 만들다. (소수들을 벡터나 리스트같은 컨테이너에 보관해도 좋다.)

2.n을 입력받고 3~n사이의 소수들로 골드바흐의 추축을 체크한다.

   나는 소수 a , b 가 있다면

    a는 3~n사이의 소수이고 (b = n - a )도 소수 일때 결과를 출력하게 하였다

   모든 소수들을 대입해봤는데 나오지않는다면 "골드바흐는틀렸다"는 문구를 출력한다.

   n=0일떄 는 종료

 

 

#include <iostream>
#include <cmath>
 
#define MAX 1000000
 
using namespace std;
 
bool isPrime[MAX+1];
 
 
//에라토스테네스 체
void Eratosthenes(int N)
{
    for(int i = 0 ; i <= N;i++)
        isPrime[i] = true;
    
    isPrime[0] = false;
    isPrime[1] = false;
    
    
    for(int i = 2; i <= sqrt(N) ;i++)
    {
        if(isPrime[i])
        {
            for(int j = 2 ; j*i<=N ;j++)
                isPrime[j*i] = false;
        }
    }
}
 
 
void printResult(int num , int a, int b)
{
    printf("%d = %d + %d\n", num, a, b);
}
 
void checkGoldbach(int num)
{
    int n = 0;
    for(int i = 3 ; i < num ; i++)
    {
        if(isPrime[i])
        {
            n = num-i;
            if(isPrime[n])
            {
                printResult(num,i,n); 
                return;
            }
        }
    }
    
    printf("Goldbach's conjecture is wrong.\n");
    
}
 
 
int main()
{
    Eratosthenes(MAX);
 
    int num = 1;
 
    while(1)
    {
        scanf("%d", &num);
        
        if(num == 0)
            break;
        
        checkGoldbach(num);
 
    }
 
    return 0;
}
 
 
 

 

반성

문제를 풀면서 게속 시간초과가 뜨길래 다른 사람의 풀이를 봐도 비슷한서 비교를 해보니

나는 cin , cout  다른사람은 scanf ,printf 사용하는게 달랐다 ,따라서 수정해보니 통과.

두 개의 연산속도 차이가 유의미하게 나는 듯 하다. 따로 알아보자. 

 

관련글 과 해결법

https://jaimemin.tistory.com/1521

ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유

 

 

https://www.geeksforgeeks.org/cincout-vs-scanfprintf/

Cin-Cout vs Scanf-Printf - GeeksforGeeks