fbpx
维基百科

埃拉托斯特尼筛法

九月 02, 2023

埃拉托斯特尼筛法（希臘語：κόσκινον Ἐρατοσθένους，英語：sieve of Eratosthenes），簡稱埃氏筛，也称素数筛，是簡單且历史悠久的筛法，用來找出一定範圍內所有質數。

原理是從2開始，將每個質數的各倍數標記成合數。一個質數的各個倍數，是一個差為此質數本身的等差數列。此為這個篩法和試除法不同的關鍵之處，後者是以質數來測試能否整除每個待測數。

質數篩是列出所有小質數的有效方法，得名於古希臘數學家埃拉托斯特尼，並且描述在另一位古希臘數學家尼科馬庫斯所著的《算術入門》中。[1]

作為現代篩法基礎的勒讓德篩法是埃拉托斯特尼篩法的簡單推廣。

算式 编辑

定出要筛数值的范围n，找出 以内的質數 。先用2去筛，把2留下，把2的倍数剔除掉；再用下個質數3筛，把3留下，把3的倍数剔除掉；接下去用下個質數5筛，把5留下，把5的倍数剔除掉，直至夠為止。

步驟 编辑

 
埃拉托斯特尼筛法

详细列出算法如下：

  1. 列出2以後所有數：
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  2. 标記第一个質数2：
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  3. 用红色标記2的倍数：
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  4. 如果最大数不大於最後一個標出的質數的平方，那么剩下的所有的数都是質数，否则回到第二步。
  1. 本例中，25大于2的平方，返回第二步：
  2. 2之後第一个質数是3，用藍色標記3的倍数：
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  1. 得到的質数是2，3。
  2. 25仍大于3的平方，再次返回第二步：
  3. 3之後第一个質数是5，用綠色標記5的倍数：
    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  4. 得到的質数是2，3，5。
  5. 25是5的平方，篩選完畢。

结论：去掉红色及綠色的数，25內的質数是2，3，5，7，11，13，17，19，23。

演算法 编辑

質數篩可用以下伪代码表示： 

输入：整数n > 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。

以上演算法可以得到小於等於n的所有質數，它的複雜度是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] = False  return [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 <= n; i++) {  is_prime[i] = true;  }  is_prime[0] = is_prime[1] = 0;  for (int i = 2; i <= n; i++) {  if (is_prime[i]) {  prime[p++] = i;  if (1ll * i * i <= n) {  for (int j = i * i; j <= n; j += i) {  is_prime[j] = 0;  }  }  }  }  return p; }

C語言新版 

#include <stdio.h> #include <stdlib.h>  /* N: positive integer  verbose: 1 -- print all prime numbers < N, 0 -- no print  return total number of prime numbers < 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 integer  unsigned long long int i, j, total; // total: number of prime numbers < 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 numbers  */  for (i = 2; i < N; i++) {  a[i] = 1;   }   // mark multiples(<N) of i as non-prime numbers  for (i = 2; i < N; i++) {  if (a[i]) { // a[i] is prime number at this point  for (j = i; j < (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 2  so when i is 3, we only start at 3 * 3  */  a[i * j] = 0;  }  }  }   // count total. print prime numbers < N if needed.  total = 0;  for (i = 2; i < N; i++) {  if (a[i]) { // i is prime number  if (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 numbers  printf("Total of prime numbers less than %llu is : %llu\n", N, a1);    a2 = eratosthenesSieve(N, 0); // not print the prime numbers  printf("Total of prime numbers less than %llu is : %llu\n", N, a2);    return 0; }

C++ 编辑 

#include <vector>  auto eratosthenes(int upperbound) {  std::vector<bool> flag(upperbound + 1, true);  flag[0] = flag[1] = false; //exclude 0 and 1  for (int i = 2; i * i <= upperbound; ++i) {  if (flag[i]) {  for (int j = i * i; j <= upperbound; j += i)  flag[j] = false;  }  }   return flag; }

R 编辑 

eratosthenes <- function(n) {  if (n == 1) return(NULL)  if (n == 2 | n == 3) return(2:n)  numbers <- 2:n  primes <- 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] <- FALSE  }  }  return(numbers[primes]) }

JavaScript 编辑 

const countPrimes = function (n) {  const isPrime = new Array(n).fill(true);   for (let i = 2; i <= Math.sqrt(n); i++) {  if (isPrime[i]) {  for (let j = i * i; j <= n; j += i) {  isPrime[j] = false;  }  }  }   let count = 0;  for (let i = 2; i < n; i++) {  if (isPrime[i]) {  count++;  }  }   return count; };

参见 编辑

参考文献 编辑

  1. ^ Nicomachus, Introduction to Arithmetic, I, 13. [1]
  • Κοσκινον Ερατοσθενους 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.

拓展阅读 编辑

  • Interactive animation (需要JavaScript) （页面存档备份，存于互联网档案馆）
  • 打印质数的各种算法 （页面存档备份，存于互联网档案馆）
  • 欧拉函数线性筛法详解 （页面存档备份，存于互联网档案馆）（欧拉函数线性筛）
  • 一般筛法求素数+快速线性筛法求素数(较好理解) （页面存档备份，存于互联网档案馆）

九月 02, 2023
埃拉托斯特尼筛法, 本條目存在以下問題, 請協助改善本條目或在討論頁針對議題發表看法, 此條目包含過多行話或專業術語, 可能需要簡化或提出進一步解釋, 2018年2月21日, 請在討論頁中發表對於本議題的看法, 並移除或解釋本條目中的行話, 此條目的语调或风格可能不適合百科全書的寫作方式, 2018年2月21日, 請根據指南協助改善这篇条目, 請在讨论页討論問題所在及加以改善, 希臘語, κόσκινον, Ἐρατοσθένους, 英語, sieve, eratosthenes, 簡稱埃氏筛, 也称素数筛, 是. 本條目存在以下問題 請協助改善本條目或在討論頁針對議題發表看法 此條目包含過多行話或專業術語 可能需要簡化或提出進一步解釋 2018年2月21日 請在討論頁中發表對於本議題的看法 並移除或解釋本條目中的行話 此條目的语调或风格可能不適合百科全書的寫作方式 2018年2月21日 請根據指南協助改善这篇条目 請在讨论页討論問題所在及加以改善 埃拉托斯特尼筛法 希臘語 koskinon Ἐratos8enoys 英語 sieve of Eratosthenes 簡稱埃氏筛 也称素数筛 是簡單且历史悠久的筛法 用來找出一定範圍內所有質數 原理是從2開始 將每個質數的各倍數標記成合數 一個質數的各個倍數 是一個差為此質數本身的等差數列 此為這個篩法和試除法不同的關鍵之處 後者是以質數來測試能否整除每個待測數 質數篩是列出所有小質數的有效方法 得名於古希臘數學家埃拉托斯特尼 並且描述在另一位古希臘數學家尼科馬庫斯所著的 算術入門 中 1 作為現代篩法基礎的勒讓德篩法是埃拉托斯特尼篩法的簡單推廣 目录 1 算式 1 1 步驟 1 2 演算法 2 程式码 2 1 Python 3 6 3 10 2 2 C語言 2 3 C 2 4 R 2 5 JavaScript 3 参见 4 参考文献 5 拓展阅读算式 编辑定出要筛数值的范围n 找出n displaystyle sqrt n nbsp 以内的質數p 1 p 2 p k displaystyle p 1 p 2 dots p k nbsp 先用2去筛 把2留下 把2的倍数剔除掉 再用下個質數3筛 把3留下 把3的倍数剔除掉 接下去用下個質數5筛 把5留下 把5的倍数剔除掉 直至夠為止 步驟 编辑 nbsp 埃拉托斯特尼筛法详细列出算法如下 列出2以後所有數 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标記第一个質数2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 用红色标記2的倍数 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 如果最大数不大於最後一個標出的質數的平方 那么剩下的所有的数都是質数 否则回到第二步 本例中 25大于2的平方 返回第二步 2之後第一个質数是3 用藍色標記3的倍数 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25得到的質数是2 3 25仍大于3的平方 再次返回第二步 3之後第一个質数是5 用綠色標記5的倍数 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 得到的質数是2 3 5 25是5的平方 篩選完畢 结论 去掉红色及綠色的数 25內的質数是2 3 5 7 11 13 17 19 23 演算法 编辑 質數篩可用以下伪代码表示 输入 整数n gt 1 设A为布尔值矩阵 下标是2至n的整数 初始时全部设成true for i 2 3 4 不超过n displaystyle sqrt n nbsp if A i 为true for j i2 i2 i i2 2i i2 3i 不超过n A j false 输出 使A i 为true的所有i 以上演算法可以得到小於等於n 的所有質數 它的複雜度是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 False return 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 1l l i i lt n for int j i i j lt n j i is prime j 0 return p C語言新版 include lt stdio h gt include lt stdlib h gt N positive integer verbose 1 print all prime numbers lt N 0 no print return 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 integer unsigned 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 numbers for i 2 i lt N i a i 1 mark multiples lt N of i as non prime numbers for i 2 i lt N i if a i a i is prime number at this point for 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 2 so when i is 3 we only start at 3 3 a 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 number if 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 numbers printf Total of prime numbers less than llu is llu n N a1 a2 eratosthenesSieve N 0 not print the prime numbers printf Total of prime numbers less than llu is llu n N a2 return 0 C 编辑 include lt vector gt auto eratosthenes int upperbound std vector lt bool gt flag upperbound 1 true flag 0 flag 1 false exclude 0 and 1 for 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 n primes 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 FALSE return 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 参见 编辑篩法 卢卡斯 莱默检验法 米勒 拉宾检验 试除法 费马素性检验 孪生素数 三胞胎素数 四胞胎素数 素数判定法则 表兄弟素数 六素数 X 1素数 勒讓德篩法 普理查篩法 英语 Sieve of Pritchard 阿特金篩法 英语 Sieve of Atkin 孫達蘭篩法 英语 Sieve of Sundaram 参考文献 编辑 Nicomachus Introduction to Arithmetic I 13 1 Koskinon Eratos8enoys 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 拓展阅读 编辑Interactive animation 需要JavaScript 页面存档备份 存于互联网档案馆 打印质数的各种算法 页面存档备份 存于互联网档案馆 筛法小结 Eratosthenes Euler 欧拉函数线性筛法详解 页面存档备份 存于互联网档案馆 欧拉函数线性筛 一般筛法求素数 快速线性筛法求素数 较好理解 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 埃拉托斯特尼筛法 amp oldid 78661675, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。