primes.cpp

/*
Prime Numbers & Factorization
Mathematical Foundation:
Sieve of Eratosthenes: Mark multiples of primes
Miller-Rabin: Probabilistic primality test
Trial Division: O(√n) factorization
Time: Sieve O(n log log n), Miller-Rabin O(k log³ n)
*/

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

// Sieve of Eratosthenes
// Related LeetCode Problems:
// 204. Count Primes
// https://leetcode.com/problems/count-primes/
// 762. Prime Number of Set Bits in Binary Representation
// https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
// 279. Perfect Squares
// https://leetcode.com/problems/perfect-squares/
// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
// 313. Super Ugly Number
// https://leetcode.com/problems/super-ugly-number/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}

// Generate all primes up to n
// Related LeetCode Problems:
// 204. Count Primes
// https://leetcode.com/problems/count-primes/
// 762. Prime Number of Set Bits in Binary Representation
// https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 279. Perfect Squares
// https://leetcode.com/problems/perfect-squares/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
vector<int> generatePrimes(int n) {
    auto is_prime = sieve(n);
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

// Segmented Sieve for large ranges
// Related LeetCode Problems:
// 204. Count Primes
// https://leetcode.com/problems/count-primes/
// 762. Prime Number of Set Bits in Binary Representation
// https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 2601. Prime Subtraction Operation
// https://leetcode.com/problems/prime-subtraction-operation/
// 2614. Prime In Diagonal
// https://leetcode.com/problems/prime-in-diagonal/
vector<bool> segmentedSieve(long long L, long long R) {
    long long lim = sqrt(R);
    auto base_primes = generatePrimes(lim);
    vector<bool> is_prime(R - L + 1, true);
    
    for (int p : base_primes) {
        long long start = max((long long)p * p, ((L + p - 1) / p) * p);
        for (long long j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }
    
    if (L == 1) is_prime[0] = false;
    return is_prime;
}

// Miller-Rabin Primality Test
// Related LeetCode Problems:
// 204. Count Primes
// https://leetcode.com/problems/count-primes/
// 762. Prime Number of Set Bits in Binary Representation
// https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
// 2601. Prime Subtraction Operation
// https://leetcode.com/problems/prime-subtraction-operation/
// 2614. Prime In Diagonal
// https://leetcode.com/problems/prime-in-diagonal/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
long long mulmod(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}

long long powmod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, mod);
        a = mulmod(a, a, mod);
        b >>= 1;
    }
    return res;
}

bool millerRabin(long long n, long long a) {
    if (n <= 1 || a >= n) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    
    long long x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (long long a : witnesses) {
        if (a >= n) break;
        if (!millerRabin(n, a)) return false;
    }
    return true;
}

// Trial Division Factorization
// Related LeetCode Problems:
// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
// 263. Ugly Number
// https://leetcode.com/problems/ugly-number/
// 313. Super Ugly Number
// https://leetcode.com/problems/super-ugly-number/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> factors;
    for (long long i = 2; i * i <= n; i++) {
        int cnt = 0;
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
        if (cnt > 0) factors.push_back({i, cnt});
    }
    if (n > 1) factors.push_back({n, 1});
    return factors;
}

// Pollard's Rho Algorithm for large number factorization
// Related LeetCode Problems:
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
long long pollardRho(long long n) {
    if (n % 2 == 0) return 2;
    
    auto f = [&](long long x) { return (mulmod(x, x, n) + 1) % n; };
    
    long long x = 2, y = 2, d = 1;
    while (d == 1) {
        x = f(x);
        y = f(f(y));
        d = __gcd(abs(x - y), n);
    }
    return d;
}

// Count divisors
// Related LeetCode Problems:
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 2427. Number of Common Factors
// https://leetcode.com/problems/number-of-common-factors/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
int countDivisors(long long n) {
    auto factors = factorize(n);
    int count = 1;
    for (auto [p, e] : factors)
        count *= (e + 1);
    return count;
}

// Sum of divisors
// Related LeetCode Problems:
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 2427. Number of Common Factors
// https://leetcode.com/problems/number-of-common-factors/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
long long sumDivisors(long long n) {
    auto factors = factorize(n);
    long long sum = 1;
    for (auto [p, e] : factors) {
        long long term = (powmod(p, e + 1, LLONG_MAX) - 1) / (p - 1);
        sum *= term;
    }
    return sum;
}

// Generate all divisors
// Related LeetCode Problems:
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 2427. Number of Common Factors
// https://leetcode.com/problems/number-of-common-factors/
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
// 1390. Four Divisors
// https://leetcode.com/problems/four-divisors/
// 1492. The kth Factor of n
// https://leetcode.com/problems/the-kth-factor-of-n/
vector<long long> getDivisors(long long n) {
    vector<long long> divisors;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) divisors.push_back(n / i);
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}

// Smallest Prime Factor for range [1,n]
// Related LeetCode Problems:
// 952. Largest Component Size by Common Factor
// https://leetcode.com/problems/largest-component-size-by-common-factor/
// 1998. GCD Sort of an Array
// https://leetcode.com/problems/gcd-sort-of-an-array/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
// 313. Super Ugly Number
// https://leetcode.com/problems/super-ugly-number/
vector<int> spf(int n) {
    vector<int> smallest(n + 1);
    iota(smallest.begin(), smallest.end(), 0);
    
    for (int i = 2; i * i <= n; i++) {
        if (smallest[i] == i) {
            for (int j = i * i; j <= n; j += i)
                if (smallest[j] == j) smallest[j] = i;
        }
    }
    return smallest;
}