[백준] 1929번 소수 구하기

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

1929번: 소수 구하기

 

 

주어진 수의 범위 내의 모든 소수 구하기

에라토스테네스의 체 알고리즘을 이용

미리 범위만큼의 boolean 배열을 생성하여 소수가 아닌 것은 false로 변경

어떤 수의 배수는 소수가 아니므로 모두 제거

0 과 1은 소수가 아니므로 제외

 

 

import java.util.*;


public class Main {

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

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        boolean[] arr = new boolean[b + 1];
        Arrays.fill(arr, true);

        for(int i = 2; i<=Math.sqrt(b); i++ ) {
            if(arr[i]){
            	int j = 2;
                while(i * j <= b) {
                    arr[i * j] = false;
                    j++;
                }
            }
        }
        arr[0] = false;
        arr[1] = false;
        
        for(int i = a; i <= b; i++) {
            if(arr[i]) {
           		System.out.println(i);
            }
        }

    }
}