Home

Welcome to the ProjectCollege wiki!

// Program to generate mersenne primes #include<bits/stdc++.h> using namespace std;

// Generate all prime numbers less than n. void SieveOfEratosthenes(int n, bool prime[]) { // Initialize all entries of boolean array // as true. A value in prime[i] will finally // be false if i is Not a prime, else true // bool prime[n+1]; for (int i=0; i<=n; i++) prime[i] = true;

for (int p=2; p*p<=n; p++)
{
    // If prime[p] is not changed, then it
    // is a prime
    if (prime[p] == true)
    {
        // Update all multiples of p
        for (int i=p*2; i<=n; i += p)
            prime[i] = false;
    }
}

}

// Function to generate mersenne primes less // than or equal to n void mersennePrimes(int n) { // Create a boolean array "prime[0..n]" bool prime[n+1];

// Generating primes using Sieve
SieveOfEratosthenes(n,prime);

// Generate all numbers of the form 2^k - 1
// and smaller than or equal to n.
for (int k=2; ((1<<k)-1) <= n; k++)
{
    long long num = (1<<k) - 1;

    // Checking whether number is prime and is
    // one less then the power of 2
    if (prime[num])
        cout << num << " ";
}

}

// Driven program int main() { int n = 31; cout << "Mersenne prime numbers smaller " << "than or equal to " << n << endl; mersennePrimes(n); return 0; }