MERSENNE PRIME IN C++ LANGUAGE
AMRUHA AHMED
10th November,2023.
Mersenne Primes are those numbers that are prime as well as they can be expressed using the formula:
2^n - 1
Where n is also a prime number.
FUNCTIONS REQUIRED:
- prime(): returns true if the number passed as parameter is prime otherwise returns false
- main():invokes prime() at appropriate intervals to check if the inputted number is a mersenne prime or not.
VARIABLES REQUIRED IN PRIME FUNCTION:
- n: passed as parameter
- i:loop counter
- ctr:count of divisors
VARIABLES REQUIRED IN MAIN FUNCTION:
- n: number to be checked for mersenne prime
- flag: to check if the number is mersenne prime or not
- i:loop counter
- result1:stores the result whether 'n' is prime or not
- result2:stores the result whether 'i' is prime or not
- power2n-to store the value of 2^i-1
ALGORITHM FOR MAIN FUNCTION:
- 1.Start
- 2.Accept a number as input from the user and store in 'n'
- 3.Invoke the prime function by passing 'n' as the parameter and store the result in result1
- 4. For i equals to 2 till i=n , the steps from (i) to (iv) need to be repeated otherwise jump to step 5:
- (i).invoke the prime function by passing 'i' as the parameter and store the result in result2
- (ii)if result2 as well as result1 are true then the steps from (iii) to (iv ) need to be repeated
- (iii)calculating 2^i-1 and storing in power2n
- (iv) if power2n is equal to n then make flag as 1 and break from the loop.
- 5.If flag==1 then 'n' is a mersenne prime otherwise 'n' is not a mersenne prime
- 6.Stop
PROGRAM:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool prime(int n)//checking if the number is prime or not
{
int i;//loop counter
int ctr=0;//count of divisors
for(i=1;i<=n;i++)
{
if(n%i==0)
ctr++;
}
if(ctr==2)
return true;//if number is prime
else
return false;//if number is not prime
}
int main()
{
int n;//number to be checked for mersenne prime
int flag=0;//flag to check if the number is mersenne prime or not
cout<<"Enter a number:";
cin>>n;
bool result1=prime(n);//stores the result whether 'n' is prime or not
for(int i=2;i<n;i++)//i is the loop counter
{
bool result2=prime(i);//stores the result whether 'i' is prime or not
if(result2==true && result1==true)//if both 'i' and 'n' are prime
{
int power2n=((int)pow(2,i))-1;//calculating 2^i-1
if(power2n==n)// if 2^i -1 is equal to n
{
flag=1;
break;
}
}
}
if(flag==1)
cout<<n<<" is a Mersenne Prime";
else
cout<<n<<" is not a Mersenne Prime";
return 0;
}
DRY RUN:
If n=7 is given as input,then result1=true since 7 is a prime number and the values of i, flag , power2n and result2 will be as follows:
OUTPUT:
Enter a number:7
7 is a Mersenne Prime