General Sieve (RAMI) - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> p_list(n+1), // List of Primes
    q_multiplicity(n+1), // Multiplicity of the smallest prime divisor
    smallest_q(n+1), // Biggest power of the smalled prime divisor
    smallest_d(n+1); // Smallest prime divisor
    p_list.reserve(n/log(n));
    std::vector<bool> is_prime(n+1,true);

    for(int i=2;i<=n;i++) if(is_prime[i])
        {
            for(int j=1,k=i;k<=n;k*=i,j++) if(is_prime[k])
                {
                    q_multiplicity[k]=j;
                    smallest_q[k]=k;
                    for(int l=2*k;l<=n;l+=k) if(is_prime[l])
                            smallest_q[l]=k;
                }
            p_list.push_back(i);
            smallest_d[i]=i;
            for(int j=2*i;j<=n;j+=i) if(is_prime[j])
                {
                    smallest_d[j] = i;
                    is_prime[j]=false;
                }
        }
    /*
     * General Sieve of multiplicative functions, or in general arithmetic functions that can be aggregated
     *  From the prime decomposition of its constituents
     * */
    std::vector<int> phi(n+1,1), // Euler Totient. phi[1] is initialized to 1
    lambda(n+1,1); // Carmichael Totient. lambda[1] is initialized to 1
    for(int i=2;i<=n;i++)
    {
        // If it is a prime power, needs to be calculated manually
        if(i == smallest_q[i])
        {
            phi[i] = smallest_q[i]  - smallest_q[i] / smallest_d[i];
            // Cases of the definition of Carmichael's totient function
            if(smallest_d[i] == 2 && i > 4)
                lambda[i] = phi[i]/2;
            else lambda[i]=phi[i];
        }
        else
        {
            phi[i] = phi[i/smallest_q[i]] * phi[smallest_q[i]];
            lambda[i] = std::lcm(lambda[i/smallest_q[i]], lambda[smallest_q[i]]);
        }
    }
}