Often this question is asked in interviews by companies and most of them apply the same old traditional method of finding prime numbers resulting in large complexity of the program. The proper solution for finding the prime numbers is the Sieve of Eratosthenes. Well, the algorithm is not so difficult, unlike its name. The basic principle here is to iteratively mark the multiples of unmarked numbers starting from 2 till the limit and then the numbers left out unmarked are primes numbers.
Let's take a series of numbers starting from 2.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now lets mark multiples of 2
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now mark multiples of 3 (Next unmarked)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now mark the multiples of next unmarked that is 5
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now mark the multiples of next unmarked and so on upto the limit.The numbers which are left unmarked till the end of iteration are Prime numbers.
Algorithm :
Input the integer numbers between 2 to n.
Let arr be array of values from 2 to n.All initialised to Zero.
Let the first number p=2.Mark all the multiples of 2 that is 2p,3p,4p...and so on and change its value in array to 1
Repeat the iteration till the end of array.
The number left with 0 value in array are prime numbers.Print them.
Pseudo Code :
arr[i]={0,0,0,......};
for i=2,3,4......
if arr[i]==0
for j=i^2, i^2+i, i^2+2i, i^2+3i.... // i^2 is used instead of 2i,3i considering the fact that the previous numbers ... are already marked
arr[j]==1;
All arr[i] which is 0 are prime numbers.
The complexity of algorithm is O(n(logn)(loglogn)) bit operations and for memory requirement O(n).You can use this algorithm to find a prime number between the range of numbers in an interview as the program has moderate complexity.There are other algorithms also but Sieve of Eratosthenes is the simplest one.
Have a look at it
Sieve of Atkin
Sieve of Sundaram
Let's take a series of numbers starting from 2.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now lets mark multiples of 2
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now mark multiples of 3 (Next unmarked)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now mark the multiples of next unmarked that is 5
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............
Now mark the multiples of next unmarked and so on upto the limit.The numbers which are left unmarked till the end of iteration are Prime numbers.
Algorithm :
Input the integer numbers between 2 to n.
Let arr be array of values from 2 to n.All initialised to Zero.
Let the first number p=2.Mark all the multiples of 2 that is 2p,3p,4p...and so on and change its value in array to 1
Repeat the iteration till the end of array.
The number left with 0 value in array are prime numbers.Print them.
Pseudo Code :
arr[i]={0,0,0,......};
for i=2,3,4......
if arr[i]==0
for j=i^2, i^2+i, i^2+2i, i^2+3i.... // i^2 is used instead of 2i,3i considering the fact that the previous numbers ... are already marked
arr[j]==1;
All arr[i] which is 0 are prime numbers.
The complexity of algorithm is O(n(logn)(loglogn)) bit operations and for memory requirement O(n).You can use this algorithm to find a prime number between the range of numbers in an interview as the program has moderate complexity.There are other algorithms also but Sieve of Eratosthenes is the simplest one.
Have a look at it
Sieve of Atkin
Sieve of Sundaram
Comments
Post a Comment