Sieve of Eratosthenes For Finding all Primes Up-to N.
Hello Friends, Welcome to my
first blog on competitive programming. Today, I am going to illuminate one fascinating mathematical concept that can
give you an edge over others in coding contest. As you might have already
figured out that today’s topic of discussion is about Sieve of primes using the
Eratosthenes’s approach. So, without wasting much time, let’s get started.
/* Before I tell you the Statement
of the problem. Let us see what are prime numbers and how we can figure out
whether a number is prime or not. */
A prime number is a whole number greater than 1
whose only factors are 1 and itself. A factor is a whole numbers that can be
divided evenly into another number.. So, to check primality of a number(lets say N), the
basic approach is to run a loop from 2 to N-1 and if any numbers in this range
divides it then the number is not a prime. We can optimize this by running loop
from 2 to N/2 as all the factors of N are less than N/2. Thus, we reduced the
loop time to N/2 instead of N in our basic approach.
Our second approach is also not
preferable as it will take linear time complexity for larger numbers. This
means we have to find out a more efficient solution. Don’t worry guys, we have
got a better solution. Yeah!! some of you might have figured out that we must
run our loop up-to square-root(N) instead of N/2. Yes, you are right but how
did you come to know this? OK, let me give you the proof for this.
Let assume that m and n are
complete factors of N (by complete factors I mean p*q=N). We will prove it by
Contradiction.
Let p> √N and
also q> √N
then, p*q>√N*√N
p*q>N but p*q=N . Therefore,
there exist at least one factor of N which is less than √N.
Hence, we reduced our loop time
from N/2 to √N. Now let us have a look at out problem
statement.
The Problem descriptions is as follows:
You are given a number N and
you have to print all the prime numbers less than this number N.
Example: N=20
Prime numbers <20: {2,3,5,7,11,13,19}
So, it is clear that the
problem here is not to check a single number whether it is prime or not but to
print all the prime numbers less than given number N. There are multiple
methods to deal with this problem. Let start with our brute force approach.
1.
Brute
Force Approach.
In brute force approach, we
will simply run a loop from 2 to N and for each number in this range(let say
X), we will check whether it is prime or not which will take √X
steps for each X in range(2,N). The complexity of the algorithm comes out to be
O(N*√N). If N is very large, then this approach seems to be time
consuming. To handle this, we have another algorithm which is called Sieve of
Eratosthenes.
2. Sieve of Eratosthenes
As the word ‘Sieve’ means
filtering out dirt elements. Similarly, in this approach we will filter out the
composite numbers leaving the prime numbers. It was first discovered by a Greek
mathematician. The steps of the algorithm is as follows:
·
Create an array A
of consecutive integers from 2 to N.
·
Initialize all the
values in array A as 0.
·
Take p=2, and make
all the multiples of 2 in array(indices which are multiples of 2) as 1.
·
Increment p and if
A[p]=0, then mark all multiples of p in array as 1. Repeat this until p<√N
·
The elements left
unmarked after the above steps in the array are the prime numbers.
Lets understand this with an
example. Let say N=50 and we have find out all the primes less than 50.
Creating an array of integers
upto 50.
Creating Array of 50 integers
Initially p=2, A[p]=0,we mark
all the multiples of 2 in array and set them as 1.
All multiples of 2 are marked
Next unmarked integer after 2
is 3 in our array because p[3]=0 , so it is unmarked. So, p=3. Now we will mark
all the multiples of 3 and set them as 1. The integers which are already marked
we will not touch them.
All multiples of 3 are marked
Next unmarked integer is 5. So,
p=5. We will mark all the multiples of 5 in the array.
All multiples of 5 are marked
Next unmarked integer is 7. So,
again we will mark all the multiples of 7 in the array.
All the multiples of 7 are marked.
We have already checked
unmarked integers upto √N i.e floor(√50)=7. So
whatever is left unmarked in the array now are all the prime numbers. Remember
we have ignored 1 because it is neither prime nor composite.
The unmarked integers are
{2,3,5,7,13,17,19,23,29,31,37,41,43,47} and are all prime numbers.
The complexity of the algorithm
is O(sqrt(n)loglog(n)) which far better than our brute force approach.
Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square)
Below I am sharing my code for Sieve of Eratosthenes.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n; //input Number N
vector<int>v(n+1); // creating a vector of size n+1 and all have default value 0.
for(int i=2;i*i<n;i++)
{
if(v[i]==0)
{
for(int p=i*2;p<=n;p+=i) // Marking all multiples of p and set them as 1.
v[p]=1;
}
}
for(int i=2;i<n;i++)
{
if(v[i]==0) // printing out all the unmarked integers which are the required prime numbers.
cout<<i<<endl;
}
}
using namespace std;
int main()
{
int n;
cin>>n; //input Number N
vector<int>v(n+1); // creating a vector of size n+1 and all have default value 0.
for(int i=2;i*i<n;i++)
{
if(v[i]==0)
{
for(int p=i*2;p<=n;p+=i) // Marking all multiples of p and set them as 1.
v[p]=1;
}
}
for(int i=2;i<n;i++)
{
if(v[i]==0) // printing out all the unmarked integers which are the required prime numbers.
cout<<i<<endl;
}
}
Kudos guys!!! You have
understood one of the most advanced and efficient algorithm. In my next blog, I
will be writing about Data Structure Most frequently used Algorithm.
Till then, Happy Coding!!
Comments
Post a Comment