Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 N보다 큰 K번째 소수 찾는 방법

개요

이 튜토리얼에서는 주어진 수 n보다 큰 수들 중에서 k번째로 등장하는 소수를 찾는 프로그램을 C++로 작성해 보겠습니다. 문제 해결의 핵심은 에라토스테네스의 체(Sieve of Eratosthenes)를 활용해 소수를 미리 걸러 두는 것입니다.

알고리즘

문제는 다음 단계를 통해 해결할 수 있습니다.

  1. 기준이 되는 수 n을 초기화합니다.
  2. 1e6(1,000,000)까지의 모든 소수를 구해 불리언 배열에 저장합니다.
  3. n + 1부터 1e6까지 반복하는 루프를 작성합니다.
    • 현재 수가 소수라면 k를 1씩 감소시킵니다.
    • k가 0이 되면 그 순간의 수 i를 반환합니다.
  4. 범위 안에서 조건을 만족하는 소수를 찾지 못하면 -1을 반환합니다.

예제 코드

위 알고리즘을 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1e6;
bool prime[MAX_SIZE + 1];
void findAllPrimes() {
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= MAX_SIZE; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= MAX_SIZE; i += p) {
                prime[i] = false;
            }
        }
    }
}
int findKthPrimeGreaterThanN(int n, int k) {
    for (int i = n + 1; i < MAX_SIZE; i++) {
        if (prime[i]) {
            k--;
        }
        if (k == 0) {
            return i;
        }
    }
    return -1;
}
int main() {
    findAllPrimes();
    int n = 5, k = 23;
    cout << findKthPrimeGreaterThanN(n, k) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

101

n = 5일 때 5보다 큰 소수는 7, 11, 13, 17, 19, ... 순서로 나열되며, 이 중 23번째 소수는 101입니다.

복잡도 분석

에라토스테네스의 체로 소수를 구하는 데 O(N log log N)의 시간이 걸리고, k번째 소수를 탐색하는 데는 최대 O(N)의 시간이 필요합니다. 공간 복잡도는 소수 여부를 저장하는 불리언 배열 때문에 O(N)입니다.

마무리

이 튜토리얼에서는 에라토스테네스의 체를 이용해 n보다 큰 k번째 소수를 효율적으로 찾는 방법을 배웠습니다. 같은 원리를 응용하면 특정 범위의 소수 개수 세기나 n번째 소수 찾기 같은 변형 문제도 쉽게 해결할 수 있습니다. 궁금한 점이 있다면 댓글로 남겨주세요.