Linear Sieve

#include <iostream>
#include <print>
#include <vector>

template<typename LowestPrime>
void sieve(int n, LowestPrime&& lowestPrime) {
    std::vector<bool> isPrime(n + 1, true);

    int i = 2;
    for (; i * i <= n; ++i) {
        if (!isPrime[i]) continue;
        lowestPrime(i, i);
        for (auto j = static_cast<int64_t>(i) * i; j <= n; j += i) {
            if (isPrime[j]) {
                lowestPrime(j, i);
                isPrime[j] = false;
            }
        }
    }
    for (; i <= n; ++i) {
        if (!isPrime[i]) continue;
        lowestPrime(i, i);
    }
}

template<typename LowestPrime>
void linearSieve(int n, LowestPrime&& lowestPrime) {
    std::vector<int> primes;
    std::vector<int> lowestPrimes(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        if (!lowestPrimes[i]) {
            primes.push_back(i);
            lowestPrimes[i] = i;
            lowestPrime(i, i);
        }
        for (auto const& p: primes) {
            if (p > lowestPrimes[i]) break;
            if (auto j = static_cast<int64_t>(i) * p; j <= n) {
                lowestPrimes[j] = p;
                lowestPrime(j, p);
            }
        }
    }
}

std::vector<int> computeMobius(int n) {
    std::vector<int> lowestPrimes(n + 1);
    sieve(n, [&](int i, int lowestPrime) {
        std::println("lowestPrimes[{}] = {}", i, lowestPrime);
        lowestPrimes[i] = lowestPrime;
    });

    std::vector<int> mobius(n + 1);
    mobius[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (i == lowestPrimes[i]) {
            mobius[i] = -1;
        } else if (int j = i / lowestPrimes[i]; lowestPrimes[j] != lowestPrimes[i]) {
            mobius[i] = -mobius[j];
        } else {
            mobius[i] = 0;
        }
    };
    return mobius;
}

#include <chrono>

int main() {
    int n = 100;
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    auto mobius = computeMobius(n);
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
}