C++에서 N보다 큰 K번째 소수

이 튜토리얼에서는 주어진 숫자 n보다 큰 k번째 소수를 찾는 프로그램을 작성할 것입니다.

• 숫자 n을 초기화합니다.
• 1e6까지의 모든 소수를 찾아 부울 배열에 저장합니다.
• n + 1에서 1e6까지 반복하는 루프를 작성하세요.
  • 현재 숫자가 소수이면 k를 감소시킵니다.
  • k가 0이면 i를 반환합니다.
• 반환 -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

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.