Finding Prime numbers - Sieve of Eratosthenes

See complete series on maths problems here:
Sieve of Eratosthenes is a very famous and efficient algorithm to generate all small prime numbers up to around 1-10 million. This is an ancient algorithm given by a Greek mathematician named Eratosthenes. We will write a simple program for prime number generation using this algorithm.

[dhariri]

Best video I've found about the Sieve of Eratosthenes so far! Great work!

[sr]

We can further optimize by reducing the number of unwanted strikes.

If i and j are co-factors of number n i.e j x i = n , then there is no need to strike off multiples of i which are < i*i (square of i ) where j < i

In other words the for loop for j can start at i ( when i=3, j can start at 3 instead of 2, because the multiples of i < (i*i) i.e for multiples of i <9 eg. 3x2=6 , would have been struck off in earlier steps )

e. In video code for i=3 j=2, ( notice j<i here ) i*j=6, but 6 has been already struck off in prev steps when (i=2, j=3)

So, when i=3, j could have started at 3 for better performance

compare starting j loop from 2 versus starting j loop at i for larger values of i

for( int i = 2 ; i <= sqrt(n) ; ++i )
{
if( primes[i] == 1 )
{
for(int j = i ; i*j <=n ; ++j) //j starts at i instead of 2
primes[i * j] = 0;
}
}

[deh]

I homeschool, but I knew the equation. However, I can't teach something if I can't explain it. I've been looking but none explained it so well to me. Now I can explain it to someone else. Thank you for taking your time to give a very good explanation.

[SYLperc]

for any grid that is a square, you only need to work out the first row of numbers. the numbers left uncrossed in the grid will be primes.

so for n=1, 000, 000, you only need to work out the first row of 1, 000 to find every prime in the 1, 000x1, 000 grid.

[borissklyar]

I propose much more simplier "matrix sieve" algorithm for finding prime numbers:

In order to find all primes (up to a given limit) in the sequence S1(p)=6p+5, (p=0, 1, 2, 3, ...):

Step 1a. Starting from 5 cross out each 5th member of the row of positive integersN(n)=0, 1, 2, 3, 4..., i.e remove the following integers: 5, 10, 15, ...

Step 1b. Starting from 5 cross out each 7th member of the row of positive integers, i.e remove the following integers: 5, 12, 19, ..

Step 2a.Starting from 23 cross out each 11th member of the row of positive integers, i.e remove the following integers: 23, 34, 45, ...

Step 2b. .Starting from 23 cross out each 13th member of the row of positive integers, i.e remove the following integers 23, 36, 49, ...



Step ia. Starting from (6i^2−1) cross out each (6i−1)th member of the row of positive integers.

Step ib. Starting from (6i^2−1) cross out each (6i+1)th member of the row of positive integers.

Remaining members of N(n) are indexes p of all primes (up to a given limit) in the sequence S1(p)=6p+5: primes are 5, 11, 17, 23, 29, ..., 41, 47, 53, 59, ..., 71, ..., 83, 89, ...

In order to find all (up to a given limit) primes in the sequence S2(p)=6p+7, (p=0, 1, 2, 3, ...):

Step 1a. Starting from 3 cross out each 5th member of the row of positive integers, i.e remove the following integers 3, 8, 13, ...

Step 1b. .Starting from 7 cross out each 7th member of the row of positive integers, i.e remove the following integers 7, 14, 21, ...

Step 2a.Starting from 19 cross out each 11th member of the row of positive integers, i.e remove the following integers 19, 30, 41, ...

Step 2b. .Starting from 27 cross out each 13th member of the row of positive integer, i.e remove the following integers 27, 40, 53, ...



Step ia.Starting from (6i^2−1−2i) cross out each (6i−1)th member of the row of positive integers.

Step ib.Starting from (6i^2−1+2i) cross out each (6i+1)th member of the row of positive integers.

Remaining members of N(n) are indexes p of all primes (up to a given limit) in the sequence S2(p)=6p+7: p=0, 1, 2, .., 4, 5, 6, .., 9, 10, 11, 12, ..., 15, 16.... and primes are7, 13, 19, ..., 31, 37, 43, ..., 61, 67, 73, 79, ..., 97, 103, ...

C++ program:

[sidddddddddddddd]

The condition for second loops is "i*j<=n". Let us suppose n=20. For i=17 and j=3, (i*j>n). So, won't 17 (i.e. a prime number) be skipped in the answer?

[manaswitadatta]

T(n) would be sqrt(n)log log n. Explanation was correct. Just a typo.

[TomLobato]

Thanks a lot. Very very helpful lessons!
I`ve noticed something confusing in 3:01. "If 2 is prime, then all multiples of 2 cannot be prime". Actually, any multiple of any positive integer cannot be prime, no matter if the factor is prime. Please let me know if I`m missing something.

[AshutoshTiwari]

I have been trying to find the most optimized method to find prime numbers.
Yours was most efficient and easiest to understand so far.
Upon experimenting, I found a more optimised solution.

In second nested for loop where j starts from 2.
we multiply j to i where i starts from 2 -> sqrt(n)

Instead of using 2 we can set j = i in the second nested loop

lets say i = 5 and j = 2 as of now

but since 5 * 2 = 10, 5 * 3 = 15, 5 * 4 = 20 where 10, 15, 20 are already covered by 2 and 3 respectively. there is no need to override those 0 from Prime[] array.
we could directly go to 5 * 5 where 25 isnt marked yet 0.

What can be the time complexity of this new approach?

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    cout.sync_with_stdio(false);
    unsigned long int n =
    unsigned long int i, j;
    int boo[n];

    for(i=0;i<n;i++)
    {
        boo[i] = 1;
    }

    for(i=2;i<=sqrt(n);i++)
    {
        if(boo[i]==1)
        {
            for(j=i;i*j<=n;j++)  // changes to be made here
            {
                boo[i*j] = 0;
            }
        }
    }

    unsigned long int counter=0;
    for(i=2;i<n;i++)
    {
        if(boo[i]==1)
        {
            cout<<i<<'\n';
            counter++;
        }
    }
    cout<<'\n'<<counter;

}

getting all prime numbers under in less then 1 seconds.

[rajeshgopidi]

Is it not possible to run the second for loop from j = i instead of starting from 2?

[maheshvangala]

Searching for a good video on seive method. found the best one

[herzalla]

If used square root of n and j=i*i;j<n;j+=i then time complexity will be O(n).

[rishabhmalhotra]

Thank you, Your legacy lives on Harshal

[sanjayidpuganti]

Actually you can have a variable inside an array subscript in C/C++, given the variable is already initialized

[lomeshdaheria]

Loved the way you explained and the optimization part as well thank you

[tomasz-rozanski]

You can optimise even more by changing the initialization in the inner loop. Instead of:
j = 2
use
j = i

[kausachan]

j = i would be fine becoz
For example, lets say we're currently computing for 13
13 * 2 = 26 (As it is 13*2, it becomes multiple of 2, so it would get striked while executing i = 2)
13 * 3 = 39 (now 13 becomes multiple of 3, so it would striked whiile executing i = 3)
13 * 4 = .... (striked while executing i = 2)
13 * 5 = .... (striked while executing i = 5)
13 * 6 = .... (striked while executing i = 2)
13 * 7 = .... (striked while executing i = 7)
13 * 8 = .... (striked while executing i = 2)
13 * 9 = .... (striked while executing i = 3)
13 * 10 = .... (striked while executing i = 2)
13 * 11 = .... (striked while executing i = 11)
13* 12 = ....(striked while executing i = 2)
13 * 13 = From here you need to start executing again
Hope this helps !

[sarcaastech]

better if we use boolean array than integer it will save some time while printing the array !


void sieve(int n)
{
bool prime[n+1];
memset(prime, true, sizeof(prime);
for(int i=2;i*i<=n;i++)
{
if(prime[i]==true)
{
for(int j=i*i;j<=n;j+=i)
prime[j]=false;
}
}
for(int i=2;i<=n;i++)
{
if(prime[i])
cout<<i<<endl;
}


}

[malharjajoo]

Great video. But wikipedia seems to have one more optimization, at every prime it seems to start cancelling it's multiples from i^2 onwards...

[gaganbedi]

8:40 for i=2, we are striking off 6 elements. Here n=15, and n/2 !=6. can you please explain how n/2 n/3 ... ?