CODEWITHSUNDEEP
c++algorithmprimes
user3521250
user3521250

Reputation: 115

Sieve of Erastothenes

I'm solving some programming problems in euler project, and i stoped in this problem:

generating the prime number

I understood the algorithm but i didn't understood one thing in the solution :

Here is a solution i took from another discussion:

void sieve_of_eratosthenes(int n)
{
    bool *sieve = new bool[n+1];

// Initialize
sieve[0]=false;
sieve[1]=false;
sieve[2]=true;

for(int i=3;i<n+1;++i)
    sieve[i]=true;

// Actual sieve
for(int i=1; i<n+1; ++i)
    //**i didnt understood what is the purpose of this condition**
    if(sieve[i]==true)
        for(int j=2;j*i<n+1;++j)
            sieve[j*i]=false;

// Output
cout << "Prime numbers are: " <<endl;
for(int i=0;i<n+1;++i)
    if (sieve[i])
        cout << i <<endl;

delete [] sieve;

}

int main()
{
    int n = 70;
    sieve_of_eratosthenes(n);
}

i understood that in the condition we try to know if the number is prime or not , but i don't understood why we jump the not prime number

any help will be useful to me, thank you

Upvotes: 0

Views: 98

Answers (2)

Bartlomiej Lewandowski
Bartlomiej Lewandowski

Reputation: 11180

A prime number is a number that has no divisors besides 1 and itself.

The aim of the sieve is to mark all multiples of the prime number as not being prime. To do so we check if the number is prime, and mark all numbers that are a multiple of that prime as not prime.

To visualize this a bit. Let's say we start from number 2.

Is 2 prime? Yes. Mark all 2*x where x < n. That would mark 2,4,6,8 etc.

Is 3 prime? Yes. Mark all 3*x -> 3,6,9 etc.

Is 4 prime? No. If we would not have this condition we would mark 4,8,16 etc as not prime, but we have already done this with 2.

Upvotes: 2

yizzlez
yizzlez

Reputation: 8805

Efficiency. Lets look at the composite number 4. Do we really need to check all the other numbers for divisibility? No, because we already checked for its prime factors.

In short, checking composite numbers is a redundant process because we check its prime factors.

Upvotes: 2

Related Questions