[백준 9020] 골드바흐의 추측

 

문제 : https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

계속 런타임 에러 나길래 화났음..ㅜㅜ

그 전문제들이랑 똑같이 에라토스테네스 체 이용해서 소수들 따로 구한 뒤에 찾아주려는데 

알고 보니까 sqrt(10000)까지만 for문을 돌리는 바람에 primes에 그 뒤의 숫자들이 추가가 안되는 상태...

그래서 지우고 10000까지 돌려주니까 정답! (11줄 주석처리, 14줄 수정!)

 

[소수 관련 문제]

2019/08/05 - [PS/백준 문제풀이] - [백준 2581] 소수

2019/08/05 - [PS/백준 문제풀이] - [백준 4948] 베르트랑 공준

 

 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
int t, n;
bool isNotPrime[10001];
vector<int> primes;
 
void eratos(){
    //int maxi = sqrt(10000);
    
    isNotPrime[1] = true;
    for(int i = 2; i <= 10000; i++){
        if(!isNotPrime[i]){
            primes.push_back(i);
            for(int j = i*i; j <= 10000; j += i)
                isNotPrime[j] = true;
        }
    }
}
 
void solve(int a){
    pair<int, int> mini;
        for(int i = 0; primes[i] < a; i++){
            int cur = primes[i];
            int another = a - cur;
            int gap = another - cur;
            
            if(gap < 0)
                break;
            
            if(!isNotPrime[another]){
                mini.first = cur;
                mini.second = another;
            }
        }
    
    cout << mini.first << " " << mini.second << '\n';
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    
    eratos();
    
    while(t--){
        cin >> n;
        solve(n);
    }
    
    return 0;
}