[알고리즘] 소수 & 에라토스테네스의 체

 

소수란 1과 자기 자신 만을 약수로 가지는 수

기본적인 소수 구하는 방법

1. 반복문을 통해 1과 자기 자신을 제외한 숫자로 나누었을때
2. 모두 % != 0 나머지가 0이 아니면 소수이다

N 의 약수는 무조건 1 ~ $\sqrt{N}$ 안에 존재한다
이 방법을 통해 시간복잡도 $O(\sqrt{n})$ 까지 감소 가능

구현예시

        double sqrt = Math.sqrt(N);
        for (int i = 2; i <= sqrt; i++) {
            if (N % i == 0)  return false;
        }

위 코드에서 sqrt 를 for 문 안에 넣으면 반복문 돌때마다 계산하므로 비효율적

for (int i = 2; i * i <= N; i++) 으로 써도 동일함

시간복잡도 : $O(\sqrt{n})$

 

에라토스테네스의 체 활용방법

특정 범위 내에서 여러 숫자가 소수인지 판별할때 유리한 알고리즘
낮은 시간복잡도, 높은 공간복잡도(메모리 사용량)

그림보면서 이해하기

1. 1 ~ N 까지 모든 수를 나열 1 ~ N 까지 모든 수를 나열
2. 아직 처리하지 않은 가장 작은 수 i 선택
3. 남은수 중 i 의 배수 모두 제거
4. 반복 (안없어지면 소수임)

 

시간복잡도 : $ O(n * log(log n)) $

 

구현 예

    static void primeCheck(int start, int end) throws IOException{
    // boolean 배열에 배열 생성 ( false 일 경우 소수임 )
    boolean[] notPrime = new boolean[end + 1];

    // 소수는 2부터 시작 (무조건 2로 해야함.. 2의 배수를 없애야 하기에)
    for (int i = 2; i*i <= end; i++) {
        // 소수가 아닌거 pass
        if (notPrime[i]) continue;
        for (int j = i * i; j <= end; j = j + i) {
            //  배수에 해당하는 애들 다 true (소수가 아님)
            notPrime[j] = true;
        }
    }
    // start 가 1일 경우 오류발생 
    if (start < 2) start = 2;
    for (int i = start; i < end + 1; i++) {
        if (!notPrime[i]) bw.write(i + "\n");
    }
}

 

 

위 코드에서 배수를 제거하는데 왜 j = i * i 부터 시작하냐면!!
i+i 부터 시작하는건 결국 2*i 인데 i 값은 처음에 2이기에 i_2 ...
즉 `_i` 이전의 배수들은 더 작은 소수들에 의해 이미 제거되었기 때문

왜 $N * \sqrt{\sqrt{N}}$ 이 아니라 $N * log(log N)$ 인가?

-> 거기까지는 생각하지말고 그냥 링크한번 보고 넘어가자;;; [링크]

참고문제
[1929] 소수 구하기
[1978] 소수찾기