จำนวนเฉพาะเมอร์เซน (Mersenne Prime) ใน C++

คำอธิบาย

ในคณิตศาสตร์ จำนวนเฉพาะเมอร์เซน (Mersenne Prime) คือจำนวนเฉพาะที่น้อยกว่ากำลังของสองหนึ่งหน่วย นั่นคือ จำนวนเฉพาะที่มีรูปแบบ M_n = 2ⁿ - 1 สำหรับจำนวนเต็ม n บางจำนวน

เขียนโปรแกรม C++ เพื่อพิมพ์จำนวนเฉพาะเมอร์เซนทั้งหมดที่น้อยกว่าจำนวนเต็มบวก n ที่รับเข้ามา

เลขชี้กำลัง n ที่ให้จำนวนเฉพาะเมอร์เซนคือ 2, 3, 5, 7,... และจำนวนเฉพาะเมอร์เซนที่ได้คือ 3, 7, 31, 127

อัลกอริทึม

1. สร้างจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ n ที่กำหนด
2. วนลูปผ่านจำนวนทุกตัวที่มีรูปแบบ 2n-1 และตรวจสอบว่ามันเป็นจำนวนเฉพาะหรือไม่

ตัวอย่างโค้ด

#include <iostream>
#include <algorithm>
using namespace std;

void generatePrimes(bool *primes, int n) {
    fill(primes, primes + n + 1, true);
    for (int p = 2; p * p <= n; ++p) {
        if (primes[p] == true) {
            for (int i = p * 2; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }
}

void mersennePrimes(int n) {
    bool primes[n + 1];
    generatePrimes(primes, n);
    for (int i = 2; ((1 << i) - 1) <= n; ++i) {
        int num = (1 << i) - 1;
        if (primes[num]) {
            cout << num << " ";
        }
    }
    cout << endl;
}

int main() {
    int n = 100;
    cout << "Mersenne primes numbers till " << n << endl;
    mersennePrimes(n);
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Mersenne primes numbers till 100
3 7 31