内容简介：给定一个数n，从2开始自增x，判断n是否被x整除。x最多自增到n的平方根即可，因为如果有大于n的平方根的值可整除n时，那么其商必定是小于n的平方根的值。代码如下：
给定一个数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实现：
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
法二：改进的求素数算法(6n+-1)
观察一下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) (6n +/- 1)
改进的代码：
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
法三：继续改进的求素数算法
还可以继续对每次跳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步的。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
编程人生（上卷）
[美] Peter Seibel / 图灵社区 / 人民邮电出版社 / 2014-12 / 39.00元
这是一本访谈笔录，记录了当今最具个人魅力的15 位软件先驱的编程生涯。包括Donald Knuth、Jamie Zawinski、Joshua Bloch、Ken Thompson等在内的业界传奇人物，为我们讲述了他们是怎么学习编程的，在编程过程中发现了什么以及他们对未来的看法，并对诸如应该如何设计软件等长久以来一直困扰很多程序员的问题谈了自己的观点。中文版分为上下卷，上卷介绍8位大师。一起来看看 《编程人生（上卷）》 这本书的介绍吧!
