<Algorithm> 197. 소수구하기(BJO)

1. 1929번 소수구하기(BJO)

   사용 알고리즘 :  에라토스체네스의 체

• 예전에 공부했던 알고리즘인데 기억할겸 다시 풀어보았다. 전에 공부하고 구현한 건 O(N^2)인데 이번엔 O(Nlog log N)으로 풀었다. 

• https://www.weeklyps.com/entry/에라토스테네스의-체-소수-구하기 이곳을 참조하여 풀었다.

• 에라토스테네스 체는 간단하게 2 부터 시작해서 자기 자신을 제외한 배수들을 지워나가는 방법이다.

코드 

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        boolean[] visited = new boolean[b+1];
        visited[1] = true;
        for(long i = 2; i <= b; i++) {
            if(!visited[(int) i]) {
                for(long j = i*i; j <= b; j+=i) {
                    visited[(int) j] = true;
                }
            }
        }
        
        for(int i = a; i <= b; i++) {
            if(!visited[i]) {
                System.out.println(i);
            }
        }
    }
}