Sieves in C++

sieve.cpp

#include <vector>
#include <bitset>
#include <iostream>
#include <chrono>

using namespace std;

const int MAXN = 10000000;

bitset<MAXN+2> bs;
vector<long long int> primes;
vector<long long int> phi(MAXN+2,0);

// calculate all primes up to upperbound
void eratosthenes() {
    bs.set();
    bs[0] = bs[1] = 0; // 0 and 1 are not primes

    for(long long int i = 2LL; i <= MAXN+1; i++) if(bs[i]) {
        primes.push_back(i); // add i to the list of primes
        // cross out all multiples of i from i*i
        for(long long int j = i*i; j <= MAXN+1; j+=i) bs[j] = 0;
    }
}

// calculate Euler's phi in a range
void euler() {
    for(int i = 1; i < MAXN; i++)
        phi[i] = i;
    for(int p = 2; p <= MAXN; p++) {
        if(phi[p] == p) {
            // first time we visit, then it is a prime
            phi[p] = p - 1;

            // use this prime to update phi at its multiples
            for(int i = 2*p; i <= MAXN; i += p)
                phi[i] = (phi[i]/p) * (p - 1);
        }
    }
}

int main() {
    chrono::time_point<chrono::steady_clock> start, end;
    start = chrono::steady_clock::now();

    eratosthenes();

    end = chrono::steady_clock::now();
    chrono::duration<double> elapsed_seconds = end - start;

    double t = elapsed_seconds.count();

    for(int i = 0; i < 100; ++i)
        cout << primes[i] << " ";
    cout << endl;

    cout << "it took " << t << " seconds to calculate " << MAXN << " primes" << endl;
    cout << "(only showing the first 100)" << endl << endl;

    start = chrono::steady_clock::now();

    euler();

    end = chrono::steady_clock::now();
    elapsed_seconds = end - start;

    t = elapsed_seconds.count();

    for(int i = 1; i <= 100; ++i)
        cout << phi[i] << " ";
    cout << endl;

    cout << "it took " << t << " seconds to calculate " << MAXN << " values of phi" << endl;
    cout << "(only showing the first 100)" << endl;

    return 0;
}