[정수론] 백준 1929

 

에라토스테네스의 체 원리

1. 주어진 범위까지 배열을 생성하고 2부터 탐색 시작.

2. 선택한 수의 모든 배수를 삭제한다.  

3. 다음 지워지지 않는 수를 선택하여 배수를 모두 삭제한다.

3. 앞의 과정을 반복한다.

 

시간 복잡도는 일반적으로 O(nlogn)이다. 뒤로 갈 수록 삭제된 데이터가 많아 탐색할 수가 적어지기 때문이다.

 

백준 1929에서 에라토스테네스의 체 적용해보기

public class 소수_구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[n+1];
        for (int i = 1; i<=n; i++) {
            a[i] = i;
        }

        for (int i =2; i<=Math.sqrt(n); i++) {
            if (a[i] == 0) continue;;
            for (int j = i+1; i<=n ;j=j+1) {
                a[i] =0;
            }
        }
        for (int i=m;i <=n; i++) {
            if (a[i] != 0) {
                System.out.println(a[i]);
            }
        }
    }
}