1929 소수 구하기

이번 문제는 에라토네스의 체를 이용하여 문제를 풀어보겠다.

 

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

 

먼저, 에라토네스의 체를 이용하면 효율적이게 소수가 아닌 수들을 구해낼 수 있다.

자세한 에라토네스의 체는 검색하길 바라며, 나는 아래와 같이 구현했다.

소수가 아닌 수를 구할 때, set에 저장하여 소수가 아닌 수를 구하고, 소수인 수를 구할 땐 set에 포함된 수인지 확인하는 방식으로 하였다.

 

import java.util.*;
public class M1929 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int M = sc.nextInt(), N = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        Set<Integer> set = new LinkedHashSet<>(N - M);
        for(int i = 2; i * i <= N; i++) {
            int num = i * i;
            while(num <= N) {
                set.add(num);
                num+=i;
            }
        }

        for(int i = M; i <= N; i++) {
            if(i < 2 || set.contains(i)) continue;
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}