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

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

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

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]

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

先實現如何找到除數

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]



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

~ ➤ 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]
>> 





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


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


拷贝下 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



#1 楼 @sunzheng91

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

#4 楼 @paranoyang

你这个算法有风险吧。

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

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

#6 楼 @fleuria

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

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

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

#10 楼 @sunzheng91

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

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

#10 楼 @sunzheng91

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

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

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

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

标准库不是内建了么?

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



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

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

#16 楼 @paranoyang

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

我怎么觉得上面给的算素数的都是直接给定一个范围,求该范围内的素数。 如果是从一个都是数字的 array 里面 select 出素数的话(该 array 里面不一定是有序、不重复的数字集),这个算法的难度是不是又上升一个等级?(至少前面提到的埃拉托斯特尼筛法就不是最优算法了)

#19 楼 @ywjno

我的算法应该是通用的吧,先排序就是了。一样的。

#20 楼 @zw963 算法是通用,但是我说的是得到最优算法 比如说[5, -7, 6, 2, -8, 2, -3, 4, 6, 0]这么一个数组, 光是进行排序是不行的,还需要:1)剔除小于 1 的数;2)去除重复数字

#9 楼 @zw963 刚刚 google 了下,印象中 haskell 有段很经典的筛法一句搞定的样子..感觉 rubinius 的那个实现该也是类似的 http://www.haskell.org/haskellwiki/Prime_numbers

#21 楼 @ywjno

不用太刻意追求算法的效率啦~~ 毕竟,那玩意儿水太深了,科学家研究的东西。

我觉得这个帖子的最大意义,还是通过更加Ruby化的方式来实现简单的算法。

事实上,因为讨论这个帖子,并因此,看了 Cruby 素数库的源码,本人受益良多啊

需要 登录 后方可回复, 如果你还没有账号请 注册新账号