| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1125
Mersenne Prime
Time Limit: 1000ms
Memory Limit: 65536kb Description
A Mersenne number is a positive integer that is one less than a power of two:
Mn=2n-1.A Mersenne prime is a Mersenne number that is prime. As of June 2009, only 47 Mersenne primes are known; the largest known prime number (243,112,609 − 1) is a Mersenne prime. They are named after 17th century French scholar Marin Mersenne(1588 – 1648), who compiled a list of Mersenne primes with exponents up to 257. His list was only partially correct. Mersenne gave little indication how he came up with his list, and its rigorous verification was completed more than two centuries later. Many greatest mathematicians made contribution on Mersenne primes, including Euler. Now you have more computing power than those great mathematicians. Given a positive integer n (n < 258), you should tell whether the Mn is a prime number. The input ends with a 0. Input
Each line of the input is a test case, which contains a positive integer n, n < 258.The last line of input is "0", which denotes the end of input. Output
For each case, output the number of n. After that, output “Prime” if the corresponding Mersenne number is prime number, otherwise output “NotPrime”
Sample Input
2 66 67 127 0 Sample Output
2:Prime 66:NotPrime 67:NotPrime 127:Prime |