幾種方法判斷一個數是否是素數
- 2020 年 4 月 5 日
- 筆記
法一：窮舉判斷一個數是否是素數
給定一個數n，從2開始自增x，判斷n是否被x整除。
x最多自增到n的平方根即可，因為如果有大於n的平方根的值可整除n時，那麼其商必定是小於n的平方根的值。
代碼如下：
def prime?(n) raise TypeError unless n.kind_of?(Integer) 2.upto(Integer.sqrt(n)) {|x| return false if n % x == 0 } return true end 這裡可以稍作改進，可以在自增時自動跳過偶數部分，這可以通過每次自增2實現：
# 2數一跳 def prime?(n) raise TypeError unless n.kind_of?(Integer) return true if n == 2 return false if n % 2 == 0 3.step(Integer.sqrt(n), 2) {|x| return false if n % x == 0 } return true end 給定一個數求出所有小於它的素數
例如給定一個數20，返回所有小於它的素數，即[2, 3, 5, 7, 11, 13, 17]。
def primes(n) arr = [] 2.upto(n) do |x| arr << x if prime?(x) end arr end 法二：改進的6數一跳的求素數算法
觀察一下100以下的所有素數：
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 從5開始，所有的素數都是6的倍數的鄰居：
5 = 6 * 1 - 1 7 = 6 * 1 + 1 11 = 6 * 2 - 1 13 = 6 * 2 + 1 17 = 6 * 3 - 1 19 = 6 * 3 + 1 23 = 6 * 4 - 1 # 25 = 6 * 4 + 1 不是素數 29 = 6 * 5 + 1 31 = 6 * 5 + 1 ... 所以有以下結論：
- 表達式
(6n +/- 1)之外的(2,3)是素數 - 從5開始的所有素數都滿足表達式
(6n +/- 1)，所有不滿足該表達式的都不是素數 - 滿足該表達式的不一定是素數
改進的代碼：
# 6數一跳 def prime?(n) raise TypeError unless n.is_a? Integer # 2 或 3 是素數 return true if n == 2 or n == 3 # 不是6n +/- 1的數不是素數 return false if n % 6 != 1 and n % 6 != 5 # 滿足6n +/- 1的數，還需進一步判斷6n兩邊的數是否是小素數的倍數 5.step(Integer.sqrt(n), 6) do |x| return false if n % x == 0 or n % (x+2) == 0 end true end 法三：繼續改進的30數一跳的求素數算法
還可以繼續對每次跳6步進行改進。
根據前面的描述，所有的素數都符合6n +/- 1模式，但其實也滿足30n +/- 1或30n +/- 7或30n +/- 11或30n +/- 13模式，簡記為30n +/- (1,7,11,13)。
例如對於如下素數，從7開始：
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 7 = 30 * 0 + 7 11 = 30 * 0 + 11 13 = 30 * 0 + 13 17 = 30 * 1 - 13 19 = 30 * 1 - 11 23 = 30 * 1 - 7 29 = 30 * 1 - 1 31 = 30 * 1 + 1 37 = 30 * 1 + 7 41 = 30 * 1 + 11 43 = 30 * 1 + 13 47 = 30 * 2 - 13 49 = 30 * 2 - 11 53 = 30 * 2 - 7 59 = 30 * 2 - 1 ... 所以：
- 表達式之外的
2,3,5也是素數 - 不滿足表達式
30n +/- (1,7,11,13)的都不是素數 - 滿足表達式
30n +/- (1,7,11,13)的不一定是素數，還需判斷該數是否能被這些小素數整除
Ruby代碼如下：
法四：Ruby官方的素數庫
Ruby官方提供了一個名為Prime的庫：https://ruby-doc.org/stdlib-2.6.5/libdoc/prime/rdoc/Prime.html
該庫使用的是惰性生成器生成素數，所以效率並不高。至少，比上面介紹的兩種改進方法要慢的多。
各種方法的效率測試
對法一、法二、法三、法四進行效率測試，比如生成400W以下的所有素數並加入到各自的數組中，比較其時間。
# 每次跳過2 def prime2?(n) raise TypeError unless n.kind_of?(Integer) return true if n == 2 3.step(Integer.sqrt(n), 2) {|x| return false if n % x == 0 } return true end # 每次跳過6 def prime6?(n) raise TypeError unless n.is_a? Integer return true if n == 2 or n == 3 return false if n % 6 != 1 or n % 6 != 5 5.step(Integer.sqrt(n), 6) do |x| return false if n % x == 0 or n % (x+2) == 0 end true end # 每次跳過30 def prime30?(n) raise TypeError unless n.is_a? Integer return true if n == 2 or n == 3 or n == 5 case n % 30 when 1, 7, 11, 13, 17, 19, 23, 29 7.step(Integer.sqrt(n), 30) do |x| return false if n % x == 0 or n % (x + 4) == 0 or n % (x + 6) == 0 or n % (x + 10) == 0 or n % (x + 12) == 0 or n % (x + 16) == 0 or n % (x + 22) == 0 or n % (x + 24) == 0 end return true else false end end # 官方Prime庫的prime?() require 'prime' require 'benchmark' prime_official_arr = [] prime2_arr = [] prime6_arr = [] prime30_arr = [] n = 4_000_000 Benchmark.bm(15) do |bm| bm.report("official") do 2.upto(n) do |x| prime_official_arr << x if Prime.prime?(x) end end bm.report("2n") do 2.upto(n) do |x| prime2_arr << x if prime2?(x) end end bm.report("6n") do 2.upto(n) do |x| prime6_arr << x if prime6?(x) end end bm.report("30n") do 2.upto(n) do |x| prime30_arr << x if prime30?(x) end end end p prime_official_arr == prime2_arr p prime_official_arr == prime6_arr p prime_official_arr == prime30_arr 測試結果：
user system total real official 24.656250 0.000000 24.656250 ( 24.711801) 2n 10.515625 0.000000 10.515625 ( 10.526535) 6n 5.562500 0.000000 5.562500 ( 5.578110) 30n 3.703125 0.015625 3.718750 ( 3.713207) true true true 可見，效率最差的是官方庫提供的惰性生成模式的Prime.prime?，效率最好的是每次跳30步的。
