内容简介：给定一个数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步的。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
JAVASCRIPT语言精髓与编程实践
周爱民 / 电子工业出版社 / 2008-3 / 68.00元
《JAVASCRIPT语言精髓与编程实践》讲述了JavaScript的语言实现与扩展，主要包括以下三个方面的内容：（1）动态、函数式语言，以及其它语言特性在JavaScript的表现与应用；（2）如何用动态函数式语言的特性来扩展JavaScript的语言特性与框架；（3）如何将JavaScript引擎整合到其它高级语言的开发过程中。一起来看看 《JAVASCRIPT语言精髓与编程实践》 这本书的介绍吧!
