[백준][1929번] 소수 구하기

문제 URL

https://www.acmicpc.net/problem/1929

나의 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        String str[] = sc.nextLine().split(" ");
        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);
        boolean[] check = new boolean[b + 1];

        // (1)
        for (int i = 2; i <= b; i++) {
            if (check[i]) continue;

            if(i>=a) sb.append(i+"\n");

            // (2)
            for (int j = i + i; j <= b; j += i) {
                check[j] = true;
            }
        }

        System.out.println(sb);
    }
}

느낀점

소수 구하기 문제다.

(1) 지정된 범위의 소수 구하기 문제는 에라토스테네스의 체 기법을 활용하는 것이 효율적이다. 여기서는 에라토스테네스의 체 기법을 활용했다.

(2) j= i*i 부터 시작하는 것이 사실 더 정확하지만 i값이 백만 이상이 될수있는데 제곱하는것은 overflow 발생가능성이 있어서 오류가 났다. 따라서 j=i+i 부터 시작해서 구했다.