跳到主要内容

素数筛(prime)

埃氏筛​

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数 n 以内的全部素数，必须把不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。

  1. 从 2 开始遍历数组，初始为 0，当该下标值为 0 说明是素数，1 为合数
  2. 每遍历到一个素数时，开始循环遍历 i 的所有倍数都标记为 1

线性筛​

  1. 利用 0 下标开始存储当前已存在素数个数， 从 1 下标到 primes[0]即所有的素数
  2. 遍历到一个数时，如果是素数，0 下标加一，且在 primes[primes[0]]位置存入该素数
  3. 对于每一个遍历到的数，进行遍历已存在素数，把两者乘积标记为合数，当当前遍历到的素数时当前数的素因子时弹出

核心代码​

/**
 * 线性筛
 * @param max 最大值
 * @returns 素数数组
 */
export function getDualPrime(max: number) {
    const primes: number[] = new Array(max + 1).fill(0);
    for (let i = 2; i <= max; i++) {
        // 当prime是0时为素数，在primes[0]中标记
        if (primes[i] === 0) primes[++primes[0]] = i;
        // 遍历所有素数与当前数的乘积
        for (let j = 1; j <= primes[0] && i * primes[j] <= max; j++) {
            // 都标记为非素数
            primes[i * primes[j]] = 1;
            // 当前遍历到的素数是i的质因子时弹出
            if (i % primes[j] === 0) break;
        }
    }
    return primes.slice(1, primes[0] + 1);
}
/**
 * 埃氏筛
 * @param max 最大值
 * @returns 素数数组
 */
export function getEratosthenesPrime(max: number) {
    const primes: number[] = new Array(max + 1).fill(0);
    const ans: number[] = [];
    primes[0] = primes[1] = 1;
    for (let i = 2; i <= max; i++) {
        if (primes[i]) continue;
        ans.push(i);
        for (let j = 2; i * j <= max; j++) primes[i * j] = 1;
    }
    return ans;
}