[백준] #4948 베르트랑 공준

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

베르트랑 공준 문제를 풀기 위해서는 이 에라토스테네스의 체를 활용한 소수판별법을 먼저 알아야한다. 이 방법을 이용하지 않고 기존의 방법처럼 무식하게 풀다보면 시간 초과가 나오게 된다.

---

에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체란 소수를 대량으로 빠르고 정확하게 구하는 방법이다. 시간 복잡도는 O(N^(1/2)).

 

이는 다음과 같은 절차로 진행된다.

1. 원하는 숫자까지의 MAX값을 true로 초기화 해준다.
2. 2부터 특정 숫자의 배수에 해당하는 숫자들을 false로 바꿔준다. (이때, 자기 자신은 제외하고 나머지 배수들만 바꾼다)
3. 이미 false로 된 숫자들은 continue하고 진행한다.

---

• JAVA로 구현한 소스코드

import java.io.*;
import java.util.ArrayList;

public class sieveOfEratosthenes {
    //public static final int MAX = 25;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int MAX = Integer.parseInt(br.readLine());
        br.close();

        ArrayList<Integer> primeList = new ArrayList<Integer>();
        boolean isPrime[] = new boolean[MAX+1];

        for (int i = 2; i <= MAX; i++)
            isPrime[i] = true;

        for (int i = 2; i <= MAX; i++) {
            if(!isPrime[i])
                continue;
            else
                primeList.add(i);
            for (int j = i*2; j <= MAX; j += i)
                isPrime[j] = false;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < primeList.size(); i++)
            bw.append(primeList.get(i) + " ");
        bw.flush();
        bw.close();
    }
}

 

• C++ 소스코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100000;

int main() {
    int n;
    cin >> n;

    vector<int> primeVector;
    bool isPrime[MAX];

    for (int i = 0; i < n; i++)
        isPrime[i] = true;

    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) continue;
        else primeVector.push_back(i);

        for (int j = i*2; j <= n; j += i)
            isPrime[j] = false;
    }

    for (int i = 0; i < primeVector.size(); i++)
        cout << primeVector[i] << " ";

    return 0;
}

---

이 에라토스테네스의 체 알고리즘을 이용한 문제가 바로 백준 #4948이다.

위의 소스코드와 차이점이라면, STL vector를 사용하지 않고, 그냥 boolean data-type에 접근하여 true인 값만 읽어와 count 해준다는 것이다. 또한, 시간초과를 방지하기 위해 미리 배열을 만들어둔 상태에서 cnt 변수만 바꾸어 출력하도록 구현하였다.

---

• C++로 구현한 백준 #4948

#include <stdio.h>
#include <vector>

using namespace std;

const int MAX = 246913;

int main() {
    bool isPrime[MAX];

    for (int i = 0; i < MAX; i++)
        isPrime[i] = true;

    for (int i = 2; i < MAX; i++) {
        for (int j = i*2; j < MAX; j += i) {
            if (!isPrime[j]) continue;
            else isPrime[j] = false;
        }
    }

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

        if (n == 0) break;
        else if (n == 1) {
            printf("1\n");
            continue;
        }
        else {
            int cnt = 0;

            for (int i = n+1; i <= 2*n; i++) {
                if (isPrime[i]) cnt++;
            }
            printf("%d\n", cnt);
        }
    }

    return 0;
}

 

---