Sieve of Eratosthenes algorithm and the prime number.
What is a prime number:
A prime number is a natural number which is greater than 1 and the only
way to write a prime number as a product is (1 X the number itself).
for example, 5 is a prime number because it can only be written as a product of 1 X 5 or 5 X 1. Similarly 7, 11, 13, 17 and so on.
Role of prime numbers:
some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time.
For example, assume that we have a ‘public key’ consisting of the product of two large prime numbers A and B. We can make this ‘public key’ public so that people can send us message encrypted by this key.

But it’s only us who knows about those two large primes A and B that forms the ‘public key’. So it will be only us who can decrypt the message. Everyone else would have to factor the product, which takes too long to be practical because of the product of two large primes A and B will be incredibly large.
Sieve of Eratosthenes algorithm:

Eratosthenes was a Greek mathematician who described an efficient way to find all primes in the range of N. Here N is 120.
Firstly we have to start from 2 the smallest prime and remove all numbers in range N that is greater than and divisible by 2, then jump to next number in this case 3 and repeat the process. After removing all numbers that are divisible by 7 in case of N = 120, we are left with only the primes.
Implementation:
We initialized two lists for primes and consecutive numbers. Then we start iterating from 2 which is the first prime number up to limit + 1. Here limit is the number in which range we want to get the primes.
Now we check if the number = 2 is present in the consecutive list. If not then append the number in the prime list. After that append every multiple of the number up to limit + 1 in the consecutive list. Because they are consecutive.
Then repeat the process for number + 1 which is 3.
When number = 4 we don’t need to check it because 4 is multiple of 2 and we append all multiple of 2 in the consecutive list.
So far so good, but this code is incredibly slow for the greater values of limit. Even limit = 1⁰⁴ takes this much execution time.
>>> from timeit import timeit
>>> test = lambda sieve: timeit(lambda: sieve(100000), number=1)
>>> reference = test(sieve)
>>> reference
>>> 75.56743338600063Though it is not the ideal way to measure the efficiency of an algorithm because it may vary from machine to machine according to their capability of processing. But I will use it as a reference for further optimization of this code.
Optimization:
First of all, instead of initializing two separate lists for two types of numbers we can initialize one boolean list of length limit. Which is by default True.
As 2 is the smallest prime we can start our loop from 3. So here number = 3.
It is unnecessary to run the loop for the value of (number)² greater than limit, so we can break. This saves a lot of work.
Now, mark all multiples of 3 as False up to limit, and increment by 2 times of number, which is (2 x 3) = 6 for the time being.
After that, we can increment the number by 2 because, as every prime is odd other than 2, we don’t need to touch evens.
At last return a list which is a comprehension of two lists. one is [2] and the other is [all odd numbers where the prime value at that index is True]
This slight change saves a huge execution time for the value of limit is 1⁰⁴, and also able to compute the result for the value of limit 1⁰⁶ in a reasonable execution time.
>>> from timeit import timeit
>>> test = lambda sieve: timeit(lambda: sieve(100000), number=1)
>>> reference = test(sieve)
>>> reference
>>> 0.005521758001123089
>>>
>>>
>>> test = lambda sieve: timeit(lambda: sieve(10000000), number=1)
>>> reference = test(sieve)
>>> reference
>>> 0.962671114000841This can be optimized further by setting a tighter limit for the loop. for example, we can use math.sqrt(limit)instead of p**2 > limit
So this is it. Hope this will help.