Số nguyên tố thứ K lớn hơn N trong C ++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm số nguyên tố thứ k lớn hơn số n đã cho.

• Khởi tạo số n.
• Tìm tất cả các số nguyên tố cho đến 1e6 và lưu trữ nó trong một mảng boolean.
• Viết một vòng lặp lặp lại từ n + 1 đến 1e6.
  • Nếu số hiện tại là số nguyên tố thì giảm dần k.
  • Nếu k bằng 0 thì trả về i.
• Trả về -1.

Ví dụ

Hãy xem mã.

#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;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

101

Kết luận

Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.