[Coding Test] inflearn(8)

1. 소수

소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를 갖는 자연수를 합성수라고 부른다.

소수 구하기 - 에라토스테네스의 체

프로그래밍 대회에서 소수 관련 문제를 풀 때 가장 자주 사용되는 방버은 바로 에라토스테네스의 체이다. 다음은 에라토스테네스의 체는 소수를 찾는 간단한 알고리즘이다.

1. 먼저 주워진 범위까지 배열을 생성한다. 1은 소수가 아니므로 삭제하고, 배열은 2부터 시작한다.
   

2. 선택한 수의 배수를 모두 삭제한다. 현재의 경우 2의 배수를 모두 삭제했다.
   

3. 다음 지워지지 않은 수를 선택한다. 즉, 3을 선택하고 선택한 수의 모든 배수를 삭제한다. 이미 지운 수는 다시 지우지 않는다.
   

4. 앞의 과정을 배열의 끝까지 반복한다.
   

5. 삭제되지 않은 수를 모두 출력한다.
   

에라토스테네스의 체의 시간 복잡도

일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))이다. 그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다. 이러한 이유 때문에 에라토스테네스의 체 기법은 현재에도 코딩 테스트에서 소수를 구하는 일반적인 방법으로 활용되고 있다.

또한, M부터 N까지 소수를 탐색하고 싶으면 2부터 N의 제곱근까지만 탐색해도 되기 때문에 시간 복잡도를 더욱 줄일 수 있다.

2. 소수 구하기 실전 문제

소수 구하기 (백준 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();
        int[] A = new int[N + 1];
        for (int i = 0; i <= N; i++) A[i] = i;
        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (A[i] == 0) continue;
            for (int j = i + i; j <= N; j += i) {
                A[j] = 0;
            }
        }
        A[1] = 0;
        for (int i = M; i <= N; i++) {
            if (A[i] != 0)
                System.out.println(A[i]);
        }
    }
}