埃拉託斯特尼篩法

埃拉託斯特尼篩法，簡稱輸入：整數"n" &gt; 1設"A"為布林值陣列，指標是2至"n"的整數，初始時全部設成true。for "i" = 2, 3, 4, ..., 不超過：if "A"["i"]為true：for "j" = "i2", "i2+i", "i2+2i", "i2+3i", ..., 不超過"n"："A"["j"] := false輸出：使"A"["i"]為true的所有"i"。以上演演算法可以得到小於等於O("n" log log "n")。程式碼.Python 3.6-3.10.def eratosthenes(n):is_prime = [True] * (n + 1)for i in range(2, int(n ** 0.5) + 1):if is_prime[i]:for j in range(i * i, n + 1, i):is_prime[j] = Falsereturn [x for x in range(2, n + 1) if is_prime[x]]print(eratosthenes(120))C語言.int prime[100005];bool is_prime[1000005];int eratosthenes(int n) {int p = 0;for (int i = 0; i &lt;= n; i++) {is_prime[i] = true;is_prime[0] = is_prime[1] = 0;for (int i = 2; i &lt;= n; i++) {if (is_prime[i]) {prime[p++] = i;if (1ll * i * i &lt;= n) {for (int j = i * i; j &lt;= n; j += i) {is_prime[j] = 0;return p;C語言新版/* N: positive integerverbose: 1 -- print all prime numbers &lt; N, 0 -- no printreturn total number of prime numbers &lt; N.return -1 when there is not enough memory.int eratosthenesSieve(unsigned long long int N, int verbose) {// prime numbers are positive, better to use largest unsiged integerunsigned long long int i, j, total; // total: number of prime numbers &lt; N_Bool *a = malloc(sizeof(_Bool) * N);if (a == NULL) {printf("No enough memory.\n");return -1;/* a[i] equals 1: i is prime number.a[i] equals 0: i is not prime number.From beginning, set i as prime number. Later filter out non-prime numbersfor (i = 2; i &lt; N; i++) {a[i] = 1;// mark multiples(&lt;N) of i as non-prime numbersfor (i = 2; i &lt; N; i++) {if (a[i]) { // a[i] is prime number at this pointfor (j = i; j &lt; (N / i) + 1; j++) {/* mark all multiple of 2 * 2, 2 * 3, as non-prime numbers;do the same for 3,4,5... 2*3 is filter out when i is 2so when i is 3, we only start at 3 * 3a[i * j] = 0;// count total. print prime numbers &lt; N if needed.total = 0;for (i = 2; i &lt; N; i++) {if (a[i]) { // i is prime numberif (verbose) {printf("%llu\n", i);total += 1;return total;int main() {unsigned long long int a1 = 0, a2 = 0, N = 10000000;a1 = eratosthenesSieve(N, 1); // print the prime numbersprintf("Total of prime numbers less than %llu is : %llu\n", N, a1);a2 = eratosthenesSieve(N, 0); // not print the prime numbersprintf("Total of prime numbers less than %llu is : %llu\n", N, a2);return 0;C++.auto eratosthenes(int upperbound) {std::vector flag(upperbound + 1, true);flag[0] = flag[1] = false; //exclude 0 and 1for (int i = 2; i * i &lt;= upperbound; ++i) {if (flag[i]) {for (int j = i * i; j &lt;= upperbound; j += i)flag[j] = false;}return flag;R.eratosthenes &lt;- function(n) {if (n == 1) return(NULL)if (n == 2 | n == 3) return(2:n)numbers &lt;- 2:nprimes &lt;- rep(TRUE, n-1)for (i in 2:floor(sqrt(n))) {if (primes[i-1]) {for (j in seq(i * i, n, i))primes[j-1] &lt;- FALSEreturn(numbers[primes])JavaScript.const countPrimes = function (n) {const isPrime = new Array(n).fill(true);for (let i = 2; i &lt;= Math.sqrt(n); i++) {if (isPrime[i]) {for (let j = i * i; j &lt;= n; j += i) {isPrime[j] = false;let count = 0;for (let i = 2; i &lt; n; i++) {if (isPrime[i]) {count++;return count;or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers", by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.