Prime numbers are very important. Most of the modern day encryption decryption relies heavily on these prime numbers. Thus generating these prime number is a good task in itself. In this article we will see how we can generate list of prime number using sieve of Eratosthenes.
What is sieve of Eratosthenes?
To find all the prime numbers less than or equal to 20, proceed as follows.
First, generate a list of integers from 2 to 20:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The first number in the list is 2. Remove every number from the list which is divisible by 2.
2 34567891011121314151617181920
Repeat the same process with next number and skip the number which is removed.
2 34567891011121314151617181920
The next number not yet crossed out in the list after 3 is 5. Cross all the multiples of 5.
2 34567891011121314151617181920
The next number not yet crossed out in the list after 5 is 7. The next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14) are also multiples of smaller primes because 7 × 7 is greater than 20. The numbers not crossed out at this point in the list are all the prime numbers below 20.
2 3 5 7 11 13 17 19
Here you get the list of prime number below 20.
Length of Longest Increasing Subsequence (LIS) in python [Dynamic Programming]
Implementation in Python
def sieve(n):
primes=[]
temp_list = [0 for x in range(0,n)]
i,j=2,2
while(i*j<n):
temp_list[i*j] = 1
j=j+1
if i*j >= n:
i,j = i+1,2
for i in range(2,n):
if temp_list[i] == 0:
primes.append(i)
return primes
if __name__ == '__main__':
n = int(input())
print sieve(n)Input for this will be like
100
Output will be below
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Now lets discuss our implementation.
What we did is make use of indices and instead of crossing the values we put 1 at those indices to make them distinguished as non prime.
We take a list of n length, fill it with 0 and then move to 4th index mark it 1 then to 6 then 8th index and mark them 1 similarly we did while crossing the numbers. Then same with 3 , 5 and so on.
We take a list like below.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
In next step we mark all the values at indices divided by 2 as 1
0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
In next step we mark all the values at indices divided by 3 as 1
0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Now mark all the values at indices divided by 5 as 1
0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Indices which are left with the value as 0 are all prime numbers.
2 3 5 7 11 13 17 19
These are all prime numbers.
This is how you generate a list of prime number using sieve method in python. If you like the article please share and subscribe.