백준 1929 소수구하기

에라토스테네스의 체

1929번: 소수 구하기Baekjoon Online Judge

Solution 1

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);

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

        for (int i = 0; i <= n; i++) {
            if (isPrime[i] && i >= m) {
                System.out.println(i);
            }
        }

    }
}

• 시간 복잡도 : 920 ms

• 공간 복잡도 : 35432 kb

• 풀이 과정 :

  • 에라토스테네스의 체를 이용하여 풀었다.

  • 그를 위해 길이가 n+1 인 boolean 배열을 만들어 소수 여부를 체크했고,

  • 출력시에는 해당 수가 m 이상인지 체크하는 조건을 추가하여 그 이전의 수는 출력되지 않도록 하였다.

Solution 2

string builder 로 답안 모두 더하여 한번만 출력하는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static boolean[] prime;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        prime = new boolean[n+1];
        prime();

        StringBuilder sb = new StringBuilder();

        for (int i = m; i <=n; i++) {
            if(!prime[i]) {
                sb.append(i).append('\n');
            }
        }

        System.out.print(sb);
    }

    private static void prime() {
        //false = 소수, true = 소수가 아님
        prime[0] = prime[1] = true;

        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            if (prime[i]) {
                continue;
            }

            for (int j = i*i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }


}

• 시간 복잡도 : 224 ms

• 공간 복잡도 : 20196 kb

• 풀이 과정 :

  • 풀이 과정은 비슷하나, BufferedReader, StringBuilder 등을 써서 입출력 시간을 단축하고자 했음

  • 또한 boolean 배열인 isPrime 을 반대로 적용하여, false 요소들만 출력되도록 하여, 최초에 true 로 초기화했던 시간을 단축했음