[백준 4948] 베르트랑 공준(소수 구하기) 이해하기 / 코드

소수 구하기

소수의 정의

자연수 n에 대하여 소수는 1과 자기자신만을 약수로 갖는다.
또한 1은 소수가 아니다.

1. 기본 방법

소수는 2 이상, n-1 이하의 수로 나누어떨어지므로
2부터 n-1까지 나눠서 0이 나오면 소수로 판별할 수 있다.
예를 들면 아래와 같이 구할 수 있다.

#include<cstdio>
int main() {
    int n;
    scanf("%d", &n);
    // n은 소수입니까?

    if(n==1) {
        printf("소수가 아님");
        return 0;
    }

    for(int i=2;i<n;i++) {
        if(n%i==0) {
            printf("소수가 아님");
            return 0;
        }
    }
    printf("소수입니다");
}

이는 1개의 수에 대해 O(n)시간에 소수판단을 할 수 있고,
n개의 수에 대해 소수판단을 하려면 O(n^2)의 시간이 걸린다.

2. 더 빠른 방법

아래와 같은 소수의 특징을 이용한다.

주어진 수 n에 대하여, n이 합성수라면 n = p * q로 표기할 수 있다.
둘중 더 작은 수 p는 제곱근n보다 작거나 같다는 성질이 있기 때문에 이를 이용하여 소수를 빠르게 구할 수 있다.

다시말해, n-1까지 모두 나눠보지 않고 제곱근n까지만 나눠지는지 확인하면 소수임을 판별할 수 있다.
이는 1개의 소수 판단에 대해 O(sqrt(n)) 시간복잡도를 갖는다.

3. 에라토스테네스의 체

특정 범위 내의 소수를 판별하는 데 쓸 수 있는 알고리즘이다.
자연수 n이 주어졌을때, 2보다 크고 자연수 n보다 작거나 같은 소수가 몇개인지를 파악할 수 있다.

첫번째)
2부터 소수를 구하고자 하는 구간의 수를 모두 배열로 선언한다
배열의 인덱스 0과 1은 사용하지 않는다.
모두 소수로 보고 true로 초기화한다.

두번째)
2부터 n까지 진행하며 소수가 아닌 수를 지워나간다.

2를 소수로 두고 2의 배수 인덱스를 모조리 false값으로 놓는다.
3을 소수로 두고 3의 배수 인덱스를 모조리 false값으로 설정한다.
4는 이미 false이므로 패스
5를 소수로 두고 5의 배수 인덱스를 모두 false로 놓는다
...를 반복한다

즉 인덱스 i가 true이면 이후 i의 배수는 약수로 i를 가지므로 i의 배수에 false를 준다.
인덱스 i가 false라는것은 이미 i가 소수가 아니라는것이므로 i의 배수들 모두 소수가 아니다(검사할 필요 없다).

4. 에라토스테네스의 체 - 더 빠르게

위의 방법이라면 소수를 O(sqrt(n))시간에 구한다 하더라도, 이는 O(n*sqrt(n)) 시간이 걸리는 문제다.
하지만 이를 2부터 n까지 체를 치는 것이 아니라 2부터 sqrt(n)까지만 체를 친다면,
O(n) 시간에 문제를 완료하게된다.

왜 sqrt(n)까지만 검사하면 되는지, sqrt(n)부터 n사이의 수에서 합성수가 모두 걸러지는지 직관적으로 이해하기 어려울 수 있다.
n의 소수판별과정에서 sqrt(n)까지만 검사하는것과 비슷한 맥락으로 이해할 수 있다.
내가 이해한 과정을 아래와 같이 정리했다.

현재 2부터 n구간의 수들에 대해 소수인지 판단하는것을 하고있다.
2~sqrt(n) 의 A구간과 sqrt(n)~n 의 B구간으로 나눴을 때,
B구간 내 임의의 합성수 m은 마찬가지로 sqrt(m)보다 작은 r, sqrt(m)보다 큰 s로 표현될 수 있다.
하지만 sqrt(m)은 A구간에 속해있기 때문에 A구간만 체를 걸러도, B구간의 합성수까지 모두 커버가 가능하다.

참고 코드

for(int i=2;i*i<n;i++) {
    if(primeArray[i]) // i가 소수일 경우,
        for(int j=i+i;j<=n;j+=i) // i의 배수부터 지운다.
            primeArray[j] = 0;
}

5. 관련 연습문제

이를 연습해볼 관련 알고리즘 문제로 백준 4948 베르트랑공준이 있다.
\

#include<cstdio>
int main() {
    int n;
    int primes[123456*2+1]; // 입력개수 제한에 맞게 배열을 선언
    primes[0] = 0; primes[1] = 0; // 0과 1은 소수가 아니므로 0으로 초기화

    for(int i=2;i<123456*2+1;i++)
        primes[i] = 1; // 모두 1로 가정. 즉 소수로 가정한다.

    for(int i=2;i*i<=123456*2+1;i++) { // i<=sqrt(123456*2+1)와 같은 종료조건
        if(primes[i]) // 소수일 경우에, 
            for(int j=i+i;j<=123456*2+1;j+=i) // 배수를 모두 체크해가며
                primes[j]=0; // false로 세팅
    }

    int cnt=0; // 정답값
    bool first = true;
    while(1) {
        scanf("%d", &n);
        if(n==0) break;
        else if(!first) printf("\n");

        cnt=0;
        for(int i=n+1;i<=2*n;i++) { // 해당 n~2n 구간에서
            cnt += primes[i]; // 소수의 개수를 모두 더한다
        }
        printf("%d", cnt);
        first = false;
    }
}