'use strict';

function* factorize(n, primes) {
    if (n <= 1)
        return [];
    let x = n;
    for (const e of primes) {
        if (e * e > x)
            break;
        if (x % e === 0) {
            let exponential = 1;
            for (x /= e; x % e === 0; exponential += 1)
                x /= e;
            yield { factor: e, exponential };
        }
    }
    if (x > 1)
        yield { factor: x, exponential: 1 };
}

function sievePrime(N) {
    if (N <= 1)
        return [];
    let tot = 0;
    const primes = [];
    const isNotPrime = new Uint8Array(N);
    for (let x = 2; x < N; ++x) {
        if (!isNotPrime[x])
            primes[tot++] = x;
        for (let i = 0; i < tot; ++i) {
            if (primes[i] * x >= N)
                break;
            isNotPrime[primes[i] * x] = 1;
            if (x % primes[i] === 0)
                break;
        }
    }
    primes.length = tot;
    return primes;
}
function sieveTotient(N) {
    if (N < 1)
        return [[], []];
    if (N === 1)
        return [[0], []];
    let tot = 0;
    const phi = new Array(N).fill(0);
    const primes = [];
    phi[1] = 1;
    for (let x = 2; x < N; ++x) {
        if (phi[x] === 0) {
            primes[tot++] = x;
            phi[x] = x - 1;
        }
        for (let i = 0; i < tot; ++i) {
            const e = primes[i];
            const target = e * x;
            if (target >= N)
                break;
            if (x % e === 0) {
                phi[target] = phi[x] * e;
                break;
            }
            phi[target] = phi[x] * (e - 1);
        }
    }
    primes.length = tot;
    return [phi, primes];
}

exports.factorize = factorize;
exports.sievePrime = sievePrime;
exports.sieveTotient = sieveTotient;