소수를 구하는 방법

소수(Prime number)는 약수가 1과 자기 자신뿐인 수를 말합니다. 소수의 반대말은 합성수(Composite number)겠죠?

1보다 큰 모든 정수는 소수거나 합성수입니다.

 

 

 

어떤 수 N이 소수인지 아닌지 판별하는 방법

N을 2부터 N-1까지의 수로 나눴을 때 나머지가 0이 나오면 합성수고, 아니면 소수입니다.

 

bool prime(int n) {
    if (n<2)
        return false;

    for (int i=2; i*i<=n; ++i)
        if (n%i == 0)
            return false;

    return true;
}

그걸 코드로 옮기면 이렇게 되는데요, 중간에 \(i*i \leq n\)이 들어가 있는데 \(i \leq \sqrt{n}\)을 실수 연산을 피하기 위해 \(i*i\)를 사용했습니다.

약수를 확인할 때는 \(n-1\)까지 확인하는 대신, \(\sqrt{n}\)까지만 확인하면 됩니다.

시간복잡도는 \(O( \sqrt{n} ) \)입니다.

 

 

 

에라토스테네스의 체

2부터 N까지 범위 안의 모든 소수를 구하려면 에라토스테네스의 체(Sieve of Eratosthenes)를 사용합니다.

알고리즘은 굉장히 간단합니다.

1. 2부터 N까지 모든 수를 쓴다
2. 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수는 소수이다
4. 그 수의 배수를 모두 지운다

 

int prime[50];     // 소수를 저장하는 배열
int pn = 0;         // 소수의 갯수
bool erased[101];   // 지워졌으면 true
int n = 100;        // 100까지의 소수 구하기

for (int i=2; i<=n; ++i) {
    if (!erased[i]) {
        prime[pn++] = i;
        for (int j=i*2; j<=n; j+=i)
            erased[j] = true;
    }
}

숫자를 지우는 작업은 인덱스를 체크하는 것으로 하고, 소수는 따로 뽑아서 순서대로 저장해 놓습니다.

제일 안쪽 for문에서 j=i*2로 시작했지만, 사실은 i*i로 하면 이미 없앤 수를 많이 건너뛸 수 있습니다.

예를 들어 5의 배수를 지울 때를 생각하면 5*2, 5*3, 5*4, 5*5, ...의 순으로 지울 겁니다. 하지만 앞의 5*2, 5*3, 5*4 까지는 이미 앞선 2, 3의 배수를 지울 때 지워졌기 때문에 5*5부터 지워나가면 됩니다.

하지만 i*i는 오버플로우의 위험이 있으니 i값이 커진다면 i*2를 사용해야 합니다.