소수 구하기 : 에라토스테네스의 체 원리

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.

이때 처음으로 선택된 숫자는 지우지 않는다.

3. 배열 끝까지 2를 반복한 후 배열에서 남아있는 모든 수를 출력한다.

 

* 시간 복잡도 : O(Nlog(logN))

 

 

예) 1 ~ 30까지 수 중 소수를 구해보자.

1. 1 ~ 30까지의 배열 생성

2. 선택한 수의 배수를 모두 삭제 -> 2의 배수를 모두 삭제

 

3. 다음 지워지지 않은 수인 3을 선택하고 3의 배수를 모두 삭제

 

4. 이를 배열의 끝까지 반복한 후 삭제되지 않은 모든 수를 출력

---

백준 온라인저지 1929번

import java.util.Scanner;

public class P1929_소수구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int M = sc.nextInt();
        int N = sc.nextInt();

        // 2 ~ N+1까지 배열 생성
        int[] arr = new int[N+1];
        for(int i=2; i<arr.length; i++) {
            arr[i] = i;
        }

        /**
         * 소수를 구할 때 N의 제곱근까지만 탐색하는 이유
         * N = a * b 라고 했을 때, a와 b는 N의 제곱근보다 클 수 없음
         * -> N의 제곱근까지만 확인해도 전체 범위의 소수 판별 가능
         *
         * ex) 16 범위까지 소수를 구할 때 16은 4 * 4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 됨
         * 4까지만 확인하고 소수 판별 진행해도 무방함
         */
        for(int i=2; i<=Math.sqrt(N); i++) {
            int num = arr[i];

            if(num == 0) {
                continue;
            }

            for(int j=i+1; j<arr.length; j++) {
                if(arr[j] % num == 0) {
                    arr[j] = 0;
                }
            }
        }

        for(int i=M; i<=N; i++) {
            if(arr[i] != 0) {
                System.out.println(arr[i]);
            }
        }
    }
}

---

백준 온라인저지 1456번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class P1456_거의소수구하기 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        // 입력값 범위가 최대 10의 14승 이므로 10의 7승까지 소수 탐색
        long[] arr = new long[10000001];
        for(int i=2; i<arr.length; i++) {
            arr[i] = i;
        }

        for(int i=2; i<=Math.sqrt(arr.length); i++) {
            long num = arr[i];

            if(num == 0) {
                continue;
            }

            for(int j=i+i; j<arr.length; j=j+i) {
                arr[j] = 0;
            }
        }

        int count = 0;
        for(int i=2; i<arr.length; i++) {
            if(arr[i] != 0) {
                // 소수인 애들
                long num = arr[i];

                while((double)arr[i] <= (double)B / (double)num) {
                    if((double)arr[i] >= (double)A / (double)num) {
                        count++;
                    }
                    num = num * arr[i];
                }
            }
        }
        System.out.println(count);
    }
}