0
#include <bits/stdc++.h>

using namespace std;


void normalSieve(int n)
{

    // prime[i] is going to store true if

    // if i*2 + 1 is composite.

    bool prime[n/2];

    memset(prime, false, sizeof(prime));


    // 2 is the only even prime so we can

    // ignore that. Loop starts from 3.

    for (int i=3 ; i*i < n; i+=2)

    {

        // If i is prime, mark all its

        // multiples as composite

        if (prime[i/2] == false)

            for (int j=i*i; j<n; j+=i*2)

                prime[j/2] = true;

    }


    // writing 2 separately

    printf("2 ");


    // Printing other primes

    for (int i=3; i<n ; i+=2)

        if (prime[i/2] == false)

            printf( "%d " , i );
}

// Driver code

int main()
{

    int n = 100 ;

    normalSieve(n);

    return 0;
}

I don't know how this sieve works but it's more efficient than what I know and i want to understand it

Andreas Wenzel
  • 22,760
  • 4
  • 24
  • 39
Stefan50C
  • 1
  • 1
    Recommended reading: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) & [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Jesper Juhl Feb 21 '23 at 21:29
  • Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. – Community Feb 21 '23 at 23:14
  • 1
    It's basically optimised to avoid handling even values (which, other than `2`, are not prime). – Peter Feb 22 '23 at 00:37

1 Answers1

0

All prime numbers are odd, so there's no point processing the even ones. Except for 2.

user253751
  • 57,427
  • 7
  • 48
  • 90