10:24PM

Ruby最快求质数算法

My Works, by Wei. 
def pn(max)
  m = (max + 1) / 2
  $pn = Array.new(max)
  for i in 1..m
    $pn[i] = (i << 1) - 1
  end
  n = m + 1
  for p in 2..m
    next unless $pn[p]
    q = p + $pn[p]
    while q < n
      $pn[q] = nil
      q += $pn[p]
    end
  end
  $pn.compact!
  $pn[0] = 2
  return $pn
end
 
t1=Time.now
pn(1_000_000)
t2=Time.now
p $pn[0..23]
p t2-t1
loop{eval(gets) rescue p $!}

这个算法是目前最快的Ruby求质数算法。

列出100万以内质数只需要2.532秒！

Tags: ,

Back Top

回复自“Ruby最快求质数算法”

  		1.

    Good work! Hard work?
    julie at 10/22/08 Wednesday 08:57AM 回复
  1. 没有任何引用。

发表回复

Back Top

注意: 评论者允许使用'@user:'的方式将自己的评论通知另外评论者。例如， ABC是本文的评论者之一，则使用'@ABC:'(不包括单引号)将会自动将您的评论发送给ABC。