{"problem":{"name":"070. Mersenne Primes","description":{"content":"As you may know, large prime numbers are in very high demand currently, and there are many large scale searches for even larger primes. Some of the largest prime numbers discovered fit a number called","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269070"},"statements":[{"statement_type":"Markdown","content":"As you may know, large prime numbers are in very high demand currently, and there are many large scale searches for even larger primes. Some of the largest prime numbers discovered fit a number called a Mersenne Prime, which is essentially any prime number than can be represented by the equation $2^p -1$. Mersenne Primes are especially interesting as they can be tested for primality with a special test called the Lucas-Lehmer test. Although you could technically solve Mersenne Primes using typical prime-number algorithms, the Lucas-Lehmer test will almost always be faster. The pseudocode for conducting the Lucas-Lehmer test for as found on Wikipedia is as follows: \n\nA single integer $p$ that represents the power of 2 in the equation $2^p -1$ to be tested.\n\nThe phrase \"true\" should be printed if the value calculated with $p$ is a Mersenne Prime, and the phrase \"false\" should be printed otherwise.\n\nMore information regarding the Lucas-Lehmer test and Mersenne Primes can be found here: https://en.wikipedia.org/wiki/Lucas-Lehmer_primality_test, https://en.wikipedia.org/wiki/Mersenne_prime.\n\n## Input\n\nA single integer $p$ that represents the power of 2 in the equation $2^p -1$ to be tested.\n\n## Output\n\nThe phrase \"true\" should be printed if the value calculated with $p$ is a Mersenne Prime, and the phrase \"false\" should be printed otherwise.\n\n[samples]\n\n## Note\n\nMore information regarding the Lucas-Lehmer test and Mersenne Primes can be found here: https://en.wikipedia.org/wiki/Lucas-Lehmer_primality_test, https://en.wikipedia.org/wiki/Mersenne_prime.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ p \\in \\mathbb{Z} $ be an integer with $ p \\geq 2 $.  \nDefine $ M_p = 2^p - 1 $.  \n\n**Constraints**  \n$ p \\geq 2 $  \n\n**Objective**  \nDetermine whether $ M_p $ is prime using the Lucas-Lehmer primality test:  \n\nDefine the sequence $ s_0 = 4 $, and for $ i \\geq 1 $,  \n$$\ns_i = (s_{i-1}^2 - 2) \\mod M_p\n$$  \nThen $ M_p $ is prime if and only if  \n$$\ns_{p-2} \\equiv 0 \\pmod{M_p}\n$$  \n\nOutput \"true\" if $ M_p $ is prime, \"false\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269070","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}