C Exercises: Generate mersenne primes within a range of numbers

Last update on December 20 2024 13:07:03 (UTC/GMT +8 hours)

Write a program in C to generate Mersenne primes within a range of numbers.

Sample Solution:

C Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

// Function to generate all primes up to 'n1'
void GenAllPrim(int n1, bool prarr1[])
{
    // Initialize an array to mark all numbers as potential primes
    for (int i = 0; i <= n1; i++)
        prarr1[i] = true;

    // Iterate through numbers and mark non-primes using the Sieve of Eratosthenes algorithm
    for (int p = 2; p * p <= n1; p++)
    {
        if (prarr1[p] == true)
        {
            for (int i = p * 2; i <= n1; i += p)
                prarr1[i] = false;
        }
    }
}

// Function to check Mersenne primes within the specified range 'nm'
void chkMerPrime(int nm)
{
    bool prarr1[nm + 1]; // Array to store prime numbers within the range
    GenAllPrim(nm, prarr1); // Generate all primes up to 'nm'

    // Iterate through powers of 2 minus 1 within the specified range to check for Mersenne primes
    for (int j = 2; ((1 << j) - 1) <= nm; j++)
    {
        long long num = (1 << j) - 1; // Calculate Mersenne number using the formula 2^j - 1

        // Check if the calculated Mersenne number is a prime and print it
        if (prarr1[num])
            printf(" %lli ", num);
    }
}

// Main function
int main()
{
    int n;
    printf("\n\n Generate Mersenne primes within a range of numbers:\n");
    printf("--------------------------------------------------------\n");
    printf(" Input an upper limit [range from 1 to upper limit]: ");
    scanf("%d", &n); // Reading the upper limit from the user

    printf(" Mersenne prime numbers are: \n");
    chkMerPrime(n); // Call function to find Mersenne primes within the specified range
    printf("\n\n");

    return 0;
}

Sample Output:

 Input a upper limit [range from 1 to upper limit]: 1000                                                      
 Mersenne prime numbers are:                                                                                  
 3  7  31  127 

Visual Presentation:

Flowchart:

C Programming Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a program in C to Check if a number is Mersenne number or not.
Next: Write a program in C to find narcissistic decimal numbers within a specific range.