Tìm số nguyên tố K-th 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 trước.

• Khởi tạo số N.
• Tìm tất cả số nguyên tố đến 1e6 và lưu trong mảng boolean.
• Viết vòng lặp từ N + 1 đến 1e6:
  • Nếu số hiện tại là nguyên tố, giảm K.
  • Nếu K bằng 0, trả về số hiện tại.
• Trả về -1 nếu không tìm thấy.

Ví dụ

Dưới đây là mã nguồn C++:

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

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

101

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.