/**
 * @file π.cpp
 * @brief Program to compute the prime counting function π(n).
 * 
 * This program computes the prime counting function, π(n) using the 
 * Sieve of Eratosthenes method.  The prime counting function is the
 * number of primes less than or equal to the argument n.
 * 
 * Compile with command: g++ --std=c++11 π.cpp -o π
 *
 * @author Richard Lesh
 * @date 2025-02-05
 * @version 1.0
 */

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

/**
 * @brief Function to compute the prime counting function π(n).
 * 
 * Function to compute the prime counting function π(n) using Sieve of Eratosthenes.
 * 
 * @param n The limit of the number of primes to count.
 * @return long The number of primes less than or equal to n.
 */
 long π(long n) {
    if (n % 2 == 1) ++n;
    size_t sieve_size = (n + 1);                    // Make sure sieve_size is even
    sieve_size >>= 1;                               // Cut in half, no need to store even's

    // prime/composite status will be stored in is_prime[i >> 1].  Leave is_prime[0] true to represent 2
    std::vector<bool> is_prime(sieve_size, true);   // all start as marked prime
    
    long sqrt_n = sqrt(n);
    for (long i = 3; i <= sqrt_n; i += 2) {         // look for primes from 3 to sqrt(n) inclusive
        if (!is_prime[i >> 1]) continue;            // if composite, continue
        for (size_t p = i * i; p <= n; p += i) {    // if prime, set multiples starting with i * i to false
            if (p % 2 == 0) continue;               // if its a multiple of 2 then continue
            is_prime[p >> 1] = false;               // otherwise mark it composite
        }
    }

    size_t count = 0;
    for (size_t i = 0; i < sieve_size; ++i) {       // count the number of primes found
        if (is_prime[i]) {
            ++count;
        }
    }
    return count;
}

int main(int argc, char** argv) {
    if (argc != 2) {
        cout << "Syntax: " << argv[0] << " <n>" << endl;
        exit(1);
    }
    long n = stoul(argv[1]);

    long result = π(n);

    cout << result << endl;

    return 0;
}