[백준] 4948 베르트랑 공준 with C++

문제설명

---

입출력 예제

---

개념

　자연수 n과 2n 사이의 소수의 개수를 출력하는 문제다. O(sqrt(N)) 보다 조금 더 세밀한 시간 조정이 필요하다. 

---

풀이

#include <iostream>
using namespace std;

bool IsPrime(long long num) 
{
    if (num <= 1) 
        return false;

    if (num == 2 || num == 3) 
        return true;

    if (num % 2 == 0 || num % 3 == 0)
        return false;

    for (long long i = 5; i * i <= num; i += 6) 
    {
        if (num % i == 0 || num % (i + 2) == 0) 
            return false;
    }

    return true;
}

int main() 
{
    int N;

    while (true)
    {
        int count = 0;
        cin >> N;

        if (N == 0)
            break;

        for (int i = N + 1; i <= 2 * N; ++i)
        {
            if (IsPrime(i))
                count++;
        }
        std::cout << count << '\n';
    }
}

　지난 소수 알고리즘과 다른 점은 바로 이부분이다.

 

bool IsPrime(long long num) 
{
    ...
    for (long long i = 5; i * i <= num; i += 6) 
    {
        ...
    }

    return true;
}

　반복문의 증감식을 i += 6으로 바꾸었는데, 소수가 아닌 숫자를 제외하는 방법 중 하나인 6k ± 1 패턴을 이용한 것이다. 즉, 소수는 6k ± 1의 형태를 가지므로, 6의 배수와 6의 배수에서 1을 더하거나 빼는 값을 가진 수는 소수가 아니다.

• 6k는 2 또는 3의 배수이므로 6k ± 2, 6k ± 3은 합성수다.
• 6k + 4 = 2(3k + 2)이므로 합성수다.
• 6k + 5는 6k ± 1 형태로 존재한다.
• 따라서 소수는 6k ± 1 형태로 존재한다.

 

　이를 이용하면 기존의 알고리즘보다 약 3배 빠르게 작동하므로 효율적으로 풀 수 있다.