Prime_Factorization.cpp

bitset<N+1> isPrime; // Using bitset for memory efficiency
vector<int> prime_count(N+1, 0); // To store the number of primes up to each index
vi prime;

void sieve() {
    isPrime.set(); // Set all bits to true
    isPrime[0] = false;
    isPrime[1] = false;
    
    prime.push_back(2);
    // Only consider odd numbers
    for (int i = 3; i * i <= N; i += 2) {
        if (isPrime[i]) {
            prime.push_back(i);
            for (int j = i * i; j <= N; j += i)  // Start from i*i, not 2*i
                isPrime[j] = false;
        }
    }

    for (int i = sqrt(N) + 1; i <= N; i++) {  // Add primes > sqrt(N)
        if (isPrime[i])
            prime.push_back(i);
    }
}
void factorization(ll n)
{
    vii v;
    for(ll i=0; prime[i]*prime[i]<=n; i++){
        if(n%prime[i]==0){
         while(n%prime[i]==0){
            v.push_back(prime[i]);
            n/=prime[i];
         }
        }
    }
    if(n!=1) v.push_back(n);
    // cout(v);
}