#8 기본수학2 - 2

백준 문제풀이

 

4948번 문제 : 베르트랑 공준

문제 :

 

소스코드 :

#include <iostream>

using namespace std;

int primeNum(int n) {
    int size = 123456 * 2 + 1;
    int a[size] = {0,1};
    int cnt = 0;

    for(int i=2; i<=n*2; i++) {
        for(int j=2; i*j<=n*2; j++) {
            a[i*j] = 1;
        }
    }
    
    for(int i=n+1; i<=n*2; i++) {
        if (a[i] == 0) {
            cnt += 1;
        }
    }
    
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int num;
    int result;
    while(true) {
        cin >> num;
        if (num == 0) {
            break;
        }
        cout << primeNum(num) << "\n";  
    }
 
    return 0;
}

 

for(int i=2; i<=n*2; i++) 이 부분에서

생각없이 n*2이 아니라 n으로 짰더니 넣은 수가 그대로 출력되서 당황했다..

잘 보고, 생각하고 코드를 작성하자

 

 

9020번 문제 : 골드바흐의 추측

문제 : 

 

소스코드 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void primeNum(int n) {
    int size = 10001;
    int a[size] = {0,1};
    vector<int> v;

    for(int i=2; i<=n; i++) {
        for(int j=2; i*j<=n; j++) {
            a[i*j] = 1;
        }
    }
 
    for(int i=2; i<=n; i++) {
        if (a[i] == 0) {
            v.push_back(i);
        }
    }
    
    // n[i]는 소수, n - n[i] 역시 소수일 경우 골드바흐 파티션 출력 가능 
    // n - n[i]가 벡터에 존재하면 n - n[i]도 소수
    int number;
    vector<int> vv;
    int min = 2147000000;
    int last;
    
    for(int i=0; i<v.size(); i++) {
        number = n - v[i];
        if(find(v.begin(), v.end(), number) != v.end()) {
            // 두 소수의 차이가 가장 작은 것을 출력하기 
            if(abs(number - v[i]) < min) {
                min = abs(number - v[i]);
                last = v[i];
            }
        }
    }
    cout << last << " " << n - last << "\n";

    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t, num;
    cin >> t;
    for(int i=0; i<t; i++) {
        cin >> num;
        primeNum(num);
    }
 
    return 0;
}