/* A Mersenne prime is a prime number that is one less than a power of two. It is a prime number of the form 2^n − 1 for some integer n. For example: Input: 3 Output: true (3 is a prime number and 3=2^2-1) Input: 31 Output: true (31 is a prime number and 31=2^5-1) Input: 17 Output: false (17 is a prime number but it is not of the form 2^n-1) Write a program to check if the user input is a Mersenne prime or not. */ #include #include #include using namespace std; bool isMersenne(const size_t& number); bool isPrime(const size_t& number); int main() { size_t range_begin; size_t range_end; // range of the numbers to be checked cin >> range_begin >> range_end; //if first number in range greater than second //just swap them if(range_begin > range_end) { swap(range_begin, range_end); } cout << "All Mersenne primes in: " << range_begin << " - " << range_end << endl << endl; for(size_t i = range_begin; i <= range_end; ++i) { if(!isPrime(i)) { continue; } if(isMersenne(i)) { cout << i << " - is Mersenne prime"; } else { cout << i << " - is not Mersenne prime"; } cout << endl; } return 0; } bool isMersenne(const size_t& number) { int power = 0; while(number > pow(2, power) - 1) { power++; if(number == pow(2, power) - 1) { return true; } } return false; } bool isPrime(const size_t& number) { if(number == 2) { return true; } //even number cannot be prime else if(number % 2 == 0) { return false; } for(size_t i = 2; i < number / 2; ++i) { if(number % i == 0) { return false; } } return true; }

[Assignment] Mersenne Prime