หาจำนวนเฉพาะลำดับที่ k ที่มากกว่า N ใน C++

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมเพื่อหาจำนวนเฉพาะลำดับที่ k ซึ่งมากกว่าตัวเลข n ที่กำหนด

กำหนดค่าเริ่มต้นของตัวเลข n
หาจำนวนเฉพาะทั้งหมดจนถึง 1e6 และเก็บในอาร์เรย์ boolean
เขียนลูปที่วนจาก n + 1 ถึง 1e6
- ถ้าตัวเลขปัจจุบันเป็นจำนวนเฉพาะ ให้ลดค่า k ลง
- ถ้า k เท่ากับศูนย์ ให้คืนค่า 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; 
}

ผลลัพธ์

หากรันโค้ดด้านบน จะได้ผลลัพธ์ดังนี้:

สรุป

หากมีข้อสงสัยเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น