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.
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.
For each case, output the number of n. After that, output “Prime” if the corresponding
Mersenne number is prime number, otherwise output “NotPrime”.
2 66 67 127 0
2:Prime 66:NotPrime 67:NotPrime 127:Prime
Migrated from old NTUJ.
2009Hefei
| No. | Testdata Range | Score |
|---|