개념

<aside> 💡 소수 판별 알고리즘 소수들을 대량으로 빠르고, 정확하게 구하는 방법

</aside>

어떤 수의 소수 여부를 확인할 때, 특정 숫자의 제곱근까지만 약수의 여부를 검증하여 빠르게 구함

수가 수를 나누면 몫이 생기고, 몫과 나누는 수 둘 중 하나는 제곱근 이하이기 때문

에라토스테네스의 체 원리

가장 먼저 소수를 판별할 범위만큼 배열을 할당, 해당하는 값을 넣고 이후에 지우는 방법을 이용

1. 배열을 생성하여 초기화
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 삭제
   1. 지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.
3. 2부터 시작해서 남아있는 수를 출력

c++

#include <stdio.h>

int number = 100000;
int a[1000001];

void primeNumberSieve() {

    // 1. 배열을 생성하여 초기화한다.
    for(int i=2;i<=number;i++) {
        a[i] = i;
    }

    // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
    // (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
    for(int i=2;i<=number;i++) {
        if(a[i]==0) continue; // 이미 지워진 수라면 건너뛰기

        // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
        for(int j=2*i;j<=number; j+=i) {
            a[j] = 0;
        }
    }

    // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
    for(int i=2;i<=number;i++) {
        if(a[i]!=0) printf("%d ", a[i]);
    }
}

int main(void) {
    primeNumberSieve();
    return 0;
}

시간복잡도

O(n^/12)

참고

[Algorithm] 에라토스테네스의 체