← 都来码 / Dolaima← 例程索引typescript/app/sieve.ts 原文

typescript/app/sieve.ts · 1124 字节 · 下载原文

// 埃拉托斯特尼筛法 —— 小应用:求 2..N 的素数并统计
// Sieve of Eratosthenes -- primes up to N, with a count
//
// 来源 / Source: Rosetta Code「Sieve of Eratosthenes」JavaScript 条目(GFDL 1.2 / CC-BY-SA 3.0)
//   https://rosettacode.org/wiki/Sieve_of_Eratosthenes
// 改写:按本仓 TypeScript 前端(类型擦除 → JavaScript 后端)的可用子集重写。

const LIMIT: number = 100;

// 0 = 未知,1 = 已划掉,2 = 素数(用整数数组当标志位,避开 JS 的对象键)
const flags: number[] = [];
for (let i: number = 0; i <= LIMIT; i = i + 1) {
    flags[i] = 0;
}

let p: number = 2;
while (p * p <= LIMIT) {
    if (flags[p] === 0) {
        let m: number = p * p;
        while (m <= LIMIT) {
            flags[m] = 1;
            m = m + p;
        }
    }
    p = p + 1;
}

let count: number = 0;
let line: string = "";
for (let n: number = 2; n <= LIMIT; n = n + 1) {
    if (flags[n] === 0) {
        count = count + 1;
        line = line + n + " ";
    }
}

print_str(line + "\n");
print_str("2.." + LIMIT + " 素数个数 / primes: " + count + "\n");