[cppchallenge] 4. 주어진 수보다 작은 가장 큰 소수를 계산하기

modern cpp challenge 책의 문제들을 푸는 과정을 작성해놓으려 한다.
 
1. 문제
2. 풀이(1)
2.1. I/O
2.2. 연산
2.3. 코드
3. 소수 구하는 방법

3.1. I/O 타입
3.2. 연산 방법

3.2.1. 에라토스테네스의 체

3.2.2. 6k ± 1 방법

3.3 결론
4. 후기
 

1. 문제

주어진 수보다 가장 작은 큰 소수를 계산하는 프로그램 구현하기

사용자에 의해 주어진 수보다 가장 작은 큰 소수를 계산하고 출력하라. 결과는 반드시 양의 정수여야 한다.          

 
 

2. 풀이(1)

필요한 코드 구조는 아래와 같다.
양의 정수 입력값 받는 부분 + 최소공배수 연산하는 부분 + 결과값 출력하는 부분
 
전 문제와 마찬가지로 main함수에서 I/O를 해결하고 최소공배수 연산 부분은 따로 함수로 처리하기로 했다.

 
 
2.1. I/O
입력값, 출력값을 unsigned long long으로 정했다. 
 
 
2.2. 연산
주어진 수보다 작은 수들 중에서 가장 큰 소수를 출력해야 하므로 주어진 수 n보다 작은 1~n-1까지의 범위 중 소수를 찾아야 한다. 그러므로 입력값을 받은 후 n-1부터 에라토스테네스의 체를 이용해 소수인지 판정한다.
 
2.3. 코드
처음에 작성한 코드는 아래와 같다.

#include<iostream>

using ull = unsigned long long;

bool is_prime(ull n)
{
    if(n <= 3)
        return n > 1;

    for(ull i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

ull compute_prime(ull n)
{
    for(ull i = n - 1; i > 0; i--)
    {
        if(is_prime(i))
        {
            std::cout << i;
            return 0;
        }
    }
}


int main()
{
    ull n;

    std::cin >> n;

    compute_prime(n);

}

 

 

시간복잡도는 O(n^sqrt(n))이고, 숫자들을 하나하나 점검하기 때문에 수가 커질수록 기하급수적으로 속도가 느려진다.
 
 
 
 

3. 소수 구하는 방법

코드 작성 후 2.2. 단계에서 고민이 생겼다.

나는 일일히 하나씩 계산하는 방법을 사용했지만, 에라토스테네스의 체와 6k ± 1 방법을 사용해보기로 하였다.
 
3.1. I/O 
연산 타입은 양의 정수 상한이 가장 큰 unsigned long long을 그대로 사용한다.
 

3.2. 연산 방법
소수를 찾는 방법은 에라토스테네스의 체와 6k ± 1 방법 2가지가 있다. 해당 2가지 방법들에 대해 정리해보겠다.
 
 

3.2.1. 에라토스테네스의 체

에라토스테네스의 체는 2~n-1까지의 모든 소수를 한 번에 구하는 알고리즘으로, 소수 여부를 배열에 저장해두고 역순으로 가장 큰 소수를 찾았다.

unsigned long long find_largest_prime(unsigned long long n) {
    if (n <= 2) return 0;

    std::vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;

    for (unsigned long long i = 2; i * i < n; ++i) {
        if (is_prime[i]) {
            for (unsigned long long j = i * i; j < n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    for (unsigned long long i = n - 1; i >= 2; --i) {
        if (is_prime[i]) return i;
    }
    return 0;
}

시간복잡도는 O(nlog log(n))이다.

 

 

 

3.2.2. 6k ± 1 방법

모든 소수는 6k ± 1로 표현될 수 있다. 이것을 증명해보면 아래와 같다.

 

모든 정수는 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5로 표현될 수 있다.

6k : 이 형태의 수는 6의 배수이므로 항상 2, 3으로 나누어 떨어진다.

6k+1 : 이 형태의 수는 2와 3으로 나누어 떨어지지 않는다.

6k+2 : 이 형태의 수는 2(3k+1)로 표현될 수 있으므로 항상 2로 나누어 떨어진다.

6k+3 : 이 형태의 수는 항상 3(2k+1)로 표현될 수 있으므로 항상 3으로 나누어 떨어진다.

6k+4 : 이 형태의 수는 항상 2(3k+2)로 표현될 수 있으므로 항상 2로 나누어 떨어진다.

6k+5 : 이 형태의 수는 6k+5 또는 6(k+1)-1로 표현될 수 있으므로 6k ± 1 형태에 해당되며, 2와 3으로 나누어 떨어지지 않는다. 

결론적으로 모든 정수 중 2와 3으로 나누어떨어지지 않는 형태는 6k+1, 6k+5 뿐이다.

모든 소수(2, 3은 제외)는 정의상 2와 3을 포함한 어떤 소수로도 나누어 떨어지지 않아야 한다. 따라서 2, 3을 제외한 모든 소수는 반드시 6k+1, 6k+5 형태여야 한다. 이 두 가지 형태는 6k ± 1로 표현할 수 있는 것이다.

 

bool is_prime(unsigned long long n) {
    if(n <= 1) return false;
    if(n <= 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(unsigned long long i = 5; i * i <= n; i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

unsigned long long find_largest_prime(unsigned long long n) {
    for (unsigned long long i = n - 1; i >= 2; --i) {
        if (is_prime(i)) return i;
    }
    return 0;
}

 

해당 방법은 소수 판별을 할 때 검사 횟수를 줄여주는 방법으로, 한 번에 한 숫자만 소수 판별할 때 적합하다. 시간복잡도는 O(√n)이다. 

 

 

 

 

3.3. 결론

6k ± 1 방법은 소수 판별시 검사 횟수를 줄여주는 방법으로, 한 번에 한 숫자의 소수를 판별할 때 효과적이다. 

에라토스테네스의 체는 n 미만 모든 소수를 한 번에 구할 수 있으며, 범위 내 모든 소수를 빠르게 찾을 때 효과적이다.나는 이 문제는 범위 내에서 가장 큰 소수를 찾는 것이므로 여러 번 소수인지 판별해야 하는 문제라고 판단했다. 그러므로 에라토스테네스의 체가 해당 문제에 더 적합하다고 생각하였다.

 
 
 

4. 후기

6k ± 1 방법은 하나의 수를 빠르게 찾을 때 효율적이고, 에라토스테네스의 체는 범위 내 모든 소수를 빠르게 찾을 때 효율적이라는 것을 알았다. 그래서 알고리즘 문제에서 에라토스테네스의 체를 주로 찾는다는 생각이 들었다. 상황에 맞게 풀이에 적합한 방법을 찾아야 하므로 해당 문제에서 무엇을 필요로 하는지 명확히 하는 것 역시 중요하다는 느낌인 문제였다.