백준4948 베르트랑 공준

에라토스테네스의 체

4948번: 베르트랑 공준Baekjoon Online Judge

Solution 1.

• 풀이방법

  • 에라토스테네스의 체를 그대로 이용하였다.

  • 다만 체크할 N 값들을 배열로 받아두고, 배열의 가장 마지막 번째 자리를 구해 해당 수 * 2 만큼만 isPrime 배열길이를 잡아 딱 필요한 구간까지만 에라토스테네스의 체가 이루어지도록 하였다.

public class Bj4948 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        List<Integer> inputs = new ArrayList<>();
        while (sc.hasNextInt()) {
            int input = sc.nextInt();
            if (input == 0) break;
            inputs.add(input);
        }

        inputs.sort(Comparator.naturalOrder());

        int max = inputs.get(inputs.size()-1) * 2;

        boolean[] isPrime = new boolean[max+1];
        //true : 소수아님, false : 소수
        isPrime[0] = isPrime[1] = true;

        for (int i = 2; i*i <= max; i++) {
            if (!isPrime[i]) {
                for (int j = i*i; j <= max; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i : inputs) {
            int count = 0;
            for (int j = i+1; j <= 2*i; j++) {
                if (!isPrime[j]) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }

        System.out.println(sb);
    }
}

Solution 2.

• 19152 kb / 248 ms

• 풀이방법

  • 역시 에라토스테네스의 체를 이용하였지만, 에라토스테네스의 체 실행 이후, 각 위치까지의 소수의 개수를 구하도록 하는 배열을 하나 더 두어, 반복문으로 계속 count 하지 않도록 하였다.

  • 시간 복잡도 면에서 훨씬 유리하다.

package practice.algorithm.math;

import java.util.Scanner;

public class Bj4948_2 {

    private static final int MAX_NUM = 123457;
    private static boolean[] isPrime = new boolean[MAX_NUM*2 + 1];
    private static int[] primeCount = new int[MAX_NUM*2 + 1];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        getPrime();
        getCount();
        StringBuilder sb = new StringBuilder();

        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n == 0) break;

            sb.append(primeCount[2 * n] - primeCount[n]).append("\n");
        }

        System.out.println(sb);
    }

    private static void getCount() {
        int count = 0;
        for (int i = 2; i < isPrime.length; i++) {
            if (!isPrime[i]) {
                count++;
            }
            primeCount[i] = count;
        }
    }

    private static void getPrime() {
        //true : 소수 아님, false: 소수임
        isPrime[0] = isPrime[1] = true;

        for (int i = 2; i <= Math.sqrt(isPrime.length); i++) {
            if (!isPrime[i]) {
                for (int j = i*i; j < isPrime.length; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }
}