070. Mersenne Primes

Codeforces

IDCF10269070

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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: A single integer $p$ that represents the power of 2 in the equation $2^p -1$ to be tested. The phrase "true" should be printed if the value calculated with $p$ is a Mersenne Prime, and the phrase "false" should be printed otherwise. More 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. ## Input A single integer $p$ that represents the power of 2 in the equation $2^p -1$ to be tested. ## Output The phrase "true" should be printed if the value calculated with $p$ is a Mersenne Prime, and the phrase "false" should be printed otherwise. [samples] ## Note More 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.

**Definitions** Let $ p \in \mathbb{Z} $ be an integer with $ p \geq 2 $. Define $ M_p = 2^p - 1 $. **Constraints** $ p \geq 2 $ **Objective** Determine whether $ M_p $ is prime using the Lucas-Lehmer primality test: Define the sequence $ s_0 = 4 $, and for $ i \geq 1 $, $$ s_i = (s_{i-1}^2 - 2) \mod M_p $$ Then $ M_p $ is prime if and only if $$ s_{p-2} \equiv 0 \pmod{M_p} $$ Output "true" if $ M_p $ is prime, "false" otherwise.

API Response (JSON)

{
  "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...",
      "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 th...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments