Ruby 发起一个算法讨论，取得素数.

zw963 · 2012年04月13日 · 最后由 zw963 回复于 2012年04月16日 · 6430 次阅读

刚才有人问。自己写了个。性能感觉还可以。作为抛砖引玉，各位大佬一定会有更精妙的实现。

def prime(m = 2, n)
  (m..n).select do |number|
    for base in (2..number-1)
      break if (number % base == 0)
    end
  end
end

p prime(10, 20)         # => [11, 13, 17, 19]
p prime(10)               # => [2, 3, 5, 7]

6 个赞

sunzheng91 #1 2012年04月13日

关于算法的效率，如果求一个区间内的素数，效率最高的是筛法，复杂度是 O(N log log N) 的。如果要求是判断一个数是否是素数，有复杂度为 O(log N) 的 Miller Rabin 算法。如果求一个数的素因数分解，有最差复杂度为 O(N^(1/4)) 的 Rho 算法。当然，在素因数分解这块，有很多比 Rho 更优的算法，这块是研究热门，因为涉及 RSA 密钥破译等问题。

juanito #2 2012年04月14日

先實現如何找到除數

def square(n)
  return n * n
end

# b 可以被 a 除嗎？
def divides?(a, b)
  return b.remainder(a) == 0  
end

# 若 n 不是質數，一定有一個除數小於或等於 sqrt(n)
# 所以只要找 1 .. sqrt(n)
def find_divisor(n, test_divisor)
  if square(test_divisor) > n
    return n
  elsif divides?(test_divisor, n)
    return test_divisor
  else
    find_divisor(n, test_divisor+1)
  end
end

再實現如何找到最小除數（從 2 找起）

def smallest_divisor(n)
    find_divisor(n, 2)
end

由於質數本身是自己的最小除數 => 找到質數

# n 是一個質數 iff 自身是最小除數
def prime?(n)
    return smallest_divisor(n) == n
end

從給定的區間找，把非質數過濾掉

def find_prime(m=2, n)
    (m..n).find_all { |i|  prime?(i) == true } 
end

p find_prime(10) # => [2, 3, 5, 7]
p find_prime(10, 20) # => [11, 13, 17, 19]

zhangyuan #3 2012年04月14日

回想起大学时候数论是核心课程，现在忘得一干二净

paranoyang #4 2012年04月14日

~ ➤ irb                                                                                                                                                       
Welcome to IRB. You are using ruby 1.9.3p0 (2011-10-30 revision 33570) [i686-linux]. Have fun ;)

def prime(m,n)
  a = (2..n).to_a
  a.each do |prime|
    a.reject!{|num| num > prime && num % prime == 0}
  end
  a.delete_if{|p| p < m }
end

>> prime(2,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]
>> prime(2,3)     #=> [2, 3]
>> prime(100,1000)
=> [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
>>

1 个赞

tassandar #5 2012年04月14日

额，貌似 ruby 有内建的素数库哦


require 'mathn'
factor,primes,result = 0,Prime.new,[]
while (f = primes.next)
    if f < 20
       result << f
    else 
       break
    end
end

fleuria #6 2012年04月14日

拷贝下 rubinius 中的 Prime 类，不知道这个算法叫什么名字呢..

class Prime
  include Enumerable

  def initialize
    @seed = 1
    @primes = []
    @counts = []
  end

  def succ
    i = -1
    size = @primes.size
    while i < size
      if i == -1
        @seed += 1
        i += 1
      else
        while @seed > @counts[i]
          @counts[i] += @primes[i]
        end
        if @seed != @counts[i]
          i += 1
        else
          i = -1
        end
      end
    end
    @primes.push @seed
    @counts.push @seed + @seed
    return @seed
  end
  alias next succ

  def each
    loop do
      yield succ
    end
  end
end

zw963 #7 2012年04月14日

#1 楼 @sunzheng91

靠，根本看不懂嘛 , 早就忘记高中学的那些 log 啥的...

zw963 #8 2012年04月14日

#4 楼 @paranoyang

你这个算法有风险吧。

a.each do |prime|
  a.reject!{|num| num > prime && num % prime == 0}
end

在迭代自身的同时，删除自身的元素。

zw963 #9 2012年04月14日

#6 楼 @fleuria

这真的是 Rubinius 的源码吗？靠，这么一大堆 if, else.

大概意思就是定义 succ 方法，获取下一个素数。然后再通过 succ 来定义 each 方法，最后混入 Enumerable 模块。之后，你可以使用任意可枚举方法，来获取下一个素数。

sunzheng91 #10 2012年04月14日

#7 楼 @zw963 筛法大致的想法是找出所有能够被 2 整除的数，如果一个数能够被 2 整除且大于 2，必然不是素数。接着，找出下一个素数，便是 3，用同样的方法除去能够被 3 整除的数。一直下去，便可得到 1..n 的所有的素数。由于在 1..n 范围内素数大致有 ln(n) 个，于是复杂度大致是 O(N log log N)。

zw963 #11 2012年04月14日

#10 楼 @sunzheng91

大概了解了你的意思了。你的这个方法貌似就是我用的算法嘛... 虽然不太一样，不过很相似哦，因为我是每一个数都去从 2..n-1 开始作为除数被除，只要有一个可以被整除，就立即剔除该数，比较下一个。

我不会算那个复杂度，到底你讲的那个复杂，还是我写的那个复杂？

zw963 #12 2012年04月14日

#10 楼 @sunzheng91

哥们儿，不得不说一句，你有点像 Matz.

juanito #13 2012年04月14日

#10 楼 @sunzheng91 其實這算法叫做 Sieve of Eratosthenes

tassandar #14 2012年04月14日

#10 楼 @sunzheng91 印象你说的算法并非是最快的，但是基本是最常用的。这个东西的水很深。。

sunzheng91 #15 2012年04月14日

#14 楼 @tassandar 的确，算法的水很深。同时，算法依不同的问题而定。就像在 1 楼的回复中描述的，如果是求 1..N 中的所有素数，筛法的复杂度几乎是无法优化的——即使将这些数字扫描一遍，复杂度也是 O(N)，而筛法算法的复杂度仅为 O(N log log N)，很低了。如果判断一个数是否为素数，自然 Miller Rabin 是最好的，多年来没有算法能够超越。至于素因数分解，算法倒是真的很多，之前说的 Rho 算法只是其中一个实现比较容易的例子。

paranoyang #16 2012年04月15日

#8 楼 @zw963 这样为什么会危险？你那个方法效率比筛选法差很多很多，我写的就是 sunzheng 的算法

night_song #17 2012年04月15日

标准库不是内建了么？

require 'mathn'
123454321.prime?
123454321.prime_division

只是实现比较 naive，大一些就搞不定了

筛法，试除法，23 生成器都有 ...

Prime.take(20).drop(10)

rubinius 那样写是因为要用 ruby 实现 ruby，而 each, range 什么的都还没有⋯⋯

附带一个 1 进制的低效实现：

def prime? n
  '1' * n !~ /^(11+)\1+$/
end

zw963 #18 2012年04月16日

#10 楼 @sunzheng91 #13 楼 @Juanito #14 楼 @tassandar #16 楼 @paranoyang #17 楼 @night_song

谢谢楼上各位，通过发起这个算法，我真的是受益良多！当然，不仅仅是素数如何实现方面。应该说设计 Ruby 的方方面面吧。我查看了一些源码，学到了一些精妙的用法。总之，受益匪浅。

#16 楼 @paranoyang

我所说的危险是：我认为在对一个数组进行迭代的时候，不应该改变这个数组的元素。即使是删除数组元素。还好是删除，如果你是迭代自身的同时插入元素，肯定会出现莫名其妙的结果，你应该通过 reject 而不是 reject!, 将筛选后结果赋值给一个新的数组。然后对这个新的数组再执行 select, 选出所需范围的素数。你连续两次用到了 reject!(还有别名 select_if), 总觉得不符合常规写法。