[백준] 1929 - 소수 구하기

계속 반복되는 문제이다. 확실히 구현 방법을 이해하고 외우자.

for문은 항상 알고자 하는 최대 범위 숫자의 제곱근까지만 탐색하면 된다.

 

추가로 코드에도 주석으로 되어 있지만, for문에 대한 설명이다.

// i에 들어오는 2의 배수부터 시작해서 자신을 더해가면서 true로 만들어준다.
// 예를 들어, 3일 경우 3*2인 6부터 시작해서 6 -> 9 -> 12 .. 하는 식으로 없애준다.
// 하지만 j = 2일 때, 이미 2의 배수들은 모두 정리되므로 j = i * 2가 아닌 j = i * i부터 탐색하면 훨씬 빨라진다.
// 즉 3일 경우, 6은 2에서 이미 정리된 수이므로 3 * 3 = 9 부터 정리한다.
// 마찬가지로 133을 예로 들면, 133 * 2 = 266은 이미 2에 의해서 정리된 값이다. 133 * 3은 3에 의해서 정리 .. 따라서 자신을 곱한 수부터 시작하면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Main T = new Main();
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] arr = T.make_prime(N);

        for(int i=M; i<=N; i++) {
            if(!arr[i]) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }

    // 소수이면 false, 소수가 아니면 true
    // boolean은 기본 false로 초기화 된다.
    public boolean[] make_prime(int Max) {
        boolean[] Prime = new boolean[Max + 1];

        //0, 1은 소수가 아니므로 true
        Prime[0] = true;
        Prime[1] = true;

        for(int i=2; i<=Math.sqrt(Max); i++) {

            if(Prime[i]) {
                continue;
            }

            // i에 들어오는 2의 배수부터 시작해서 자신을 더해가면서 true로 만들어준다.
            // 예를 들어, 3일 경우 3*2인 6부터 시작해서 6 -> 9 -> 12 .. 하는 식으로 없애준다.
            // 하지만 j = 2일 때, 이미 2의 배수들은 모두 정리되므로 j = i * 2가 아닌 j = i * i부터 탐색하면 훨씬 빨라진다.
            // 즉 3일 경우, 6은 2에서 이미 정리된 수이므로 3 * 3 = 9 부터 정리한다.
            // 마찬가지로 133을 예로 들면, 133 * 2 = 266은 이미 2에 의해서 정리된 값이다. 133 * 3은 3에 의해서 정리 .. 따라서 자신을 곱한 수부터 시작하면 된다.
            for(int j = i * i; j<=Max; j = j + i) {
                Prime[j] = true;
            }
        }

        return Prime;
    }
}