sieve of prime.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>

#define fi first
#define sc second
#define MOD7 1000000007
#define MAX_SIEVE 1000001
#define MAX_INT 2000000001

using namespace std;

typedef pair<int,int> ii;
typedef vector<pair<int,int> > vii;

bitset<MAX_SIEVE> mybits;
vector<long long> primes;

inline void sieve()
{
    long long i,j;
    mybits.set();
    primes.push_back(2);
    for(i=3; i<MAX_SIEVE; i+=2)
    {
        if(mybits[i])
        {
            for(j=i*i; j<MAX_SIEVE; j+=(i<<1))
            {
                mybits[j]=0;
            }
            primes.push_back(i);
        }
    }
}

int main()
{
    sieve();

    for(int i=0; i<(int)primes.size(); i++)
    {
        printf("%lld\n",primes[i]);
    }

    return 0;
}