FANDOM


Eratosthenes篩法是一種用已知的質數尋找其他質數的方法。

方法编辑

若要找出不大於任意正整數N的質數,

  • 首先,將不大於\sqrt{N}的所有質數列出來。
  • 然後將所有介於\sqrt{N}N之間的所有(正)整數,以上一步驟中列出的質數試除,將其中可被除盡的數給刪除,再將剩下的數以另一質數試除,之後一樣將可除盡的數給刪去,如此反覆。剩下來的數即是不能被任何將不大於\sqrt{N}的質數整除者,即為質數。

例若要找不大於32的質數,首先取25的平方根,也就是4\sqrt{2},(正整數中)不大於4\sqrt{2}的質數有235三個,然後列出5到25間的每個數,也就是以下幾個數:

567891011121314151617181920212223242526272829303132

然後先將這些數以2除一次,得以下數列:

5791113151719212325272931

注意68101214161820222426283032全都可被2給除盡,因此剩下的數都不可被2給除盡

然後再將剩下的數以3除一次,得以下數列:

571113171923252931

注意9152127可被3給除盡,因此剩下的數不可被2或3給除盡。

然後再將剩下的數以5除一次,得以下數列:

5711131719232931

25在此被刪去,剩下的數不可被2、3或5給除盡,它們都是不大於32的質數,用這些數可再去尋找所有不大於1024(1024 = 32^2)的質數。

參見编辑

您使用了广告屏蔽软件!


Wikia通过广告运营为用户提供免费的服务。我们对用户通过嵌入广告屏蔽软件访问网站进行了使用调整。

如果您使用了广告屏蔽软件,将无法使用我们的服务。请您移除广告屏蔽软件,以确保页面正常加载。