效率比较:几种方法判断一个数是否是素数

回到Ruby系列文章


法一:穷举判断一个数是否是素数

给定一个数n,从2开始自增x,判断n是否被x整除。

x最多自增到n的平方根即可,因为如果有大于n的平方根的值可整除n时,那么其商必定是小于n的平方根的值。

代码如下:

1
2
3
4
5
6
7
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实现:

1
2
3
4
5
6
7
8
9
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]

1
2
3
4
5
6
7
def primes(n)
arr = []
2.upto(n) do |x|
arr << x if prime?(x)
end
arr
end

法二:改进的求素数算法(6n+-1)

观察一下100以下的所有素数:

1
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的倍数的邻居:

1
2
3
4
5
6
7
8
9
10
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
...

所以有以下结论:

  1. 表达式(6n +/- 1)之外的(2,3)是素数
  2. 从5开始的所有素数都满足表达式(6n +/- 1),所有不满足该表达式的都不是素数
  3. 满足该表达式的不一定是素数

改进的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 +/- 130n +/- 730n +/- 1130n +/- 13模式,简记为30n +/- (1,7,11,13)

例如对于如下素数,从7开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
...

所以:

  1. 表达式之外的2,3,5也是素数
  2. 不满足表达式30n +/- (1,7,11,13)的都不是素数
  3. 满足表达式30n +/- (1,7,11,13)的不一定是素数,还需判断该数是否能被这些小素数整除

Ruby代码如下:

法四:Ruby官方的素数库

Ruby官方提供了一个名为Prime的库:https://ruby-doc.org/stdlib-2.6.5/libdoc/prime/rdoc/Prime.html

该库使用的是惰性生成器生成素数,所以效率并不高。至少,比上面介绍的两种改进方法要慢的多。

各种方法的效率测试

对法一、法二、法三、法四进行效率测试,比如生成400W以下的所有素数并加入到各自的数组中,比较其时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# 每次跳过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

测试结果:

1
2
3
4
5
6
7
8
                      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步的。

文章作者: 骏马金龙
文章链接: http://www.junmajinlong.com/ruby/is_prime/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 骏马金龙
打赏我