Python Collections

Mersenne primes are a specific type of prime numbers that are extremely important in the field of computing, number theory and cryptography. They're defined as any prime number that can also be written in the form `2^n - 1` (for any integer `n`).
In this project, you'll be tasked with reading 1 million prime numbers form a text file, and identifying the Mersenne primes in there. All using Python lists and sets!

All our Data Science projects include bite-sized activities to test your knowledge and practice in an environment with constant feedback.

All our activities include solutions with explanations on how they work and why we chose them.

codevalidated

Write the function `is_mersenne`

that receives a single prime number `p`

and returns `True`

if it is a Mersenne prime, or `False`

otherwise.

codevalidated

Now it's time to find which of the prime numbers in the `primes`

variable are indeed Mersenne primes. Find all Mersenne primes and store them in the variable `mersenne_primes`

. Your list will contain the elements `[3, 7, 31, 127, ...]`

.

codevalidated

Create a list of Mersenne numbers from `1`

up to the one that is larger than the largest prime in the list of primes. That is, suppose our list of primes contained the first 12 primes: `[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]`

You should start calculating all integers starting from 1

```
1 = (2^1) - 1 = 1
2 = (2^2) - 1 = 3
3 = (2^3) - 1 = 7
4 = (2^4) - 1 = 15
5 = (2^5) - 1 = 31
6 = (2^6) - 1 = 63 <<<< 63 is LARGER than the largest prime in our list, which is 37. This is NOT included.
```

In this case, your list should contain only the mersenne numbers: `[1, 3, 7, 15, 31]`

.

codevalidated

We'll use the list `mersenne_numbers`

to check which numbers in `primes`

are Mersenne numbers. So, the ultimate efficient gain will be to turn `mersenne_numbers`

into a set, as the operations of membership in sets are `O(1)`

.

Transform the variable `mersenne_numbers`

into a set containing the same elements.

codevalidated

Now, create a new variable `efficient_mersenne_primes`

that contains all the mersenne numbers (same as before), but this time, check if the prime is a mersenne using the set `mersenne_numbers`

created in the previous activity.

Author

This project is part of

Explore other projects