2007-07-10

求50以内的素数，算法分析。

关键字: 求素数

求50以内的素数，以下算法做了很大程度的优化。拿出来与大家分析，望有更好的优化算法。

$arr=[ ]      #建立一个全局数组  $arr
$arr[0]=2   #第一个位置值存入2

 def add_prime(n)    #定义方法  将 n以内的奇素数加入$arr

    3.step(n,2){|num|$arr <<num  if is_prime?num }   
       #从3开始，取50以内的奇数，并判断将素数存入arr数组中
      
 end
 
 def  is_prime?(number)   #定义方法  判断一个数是否是素数
    j=0                                #数组下标
         
      #算法分析：首先判断该数是否大于小于本身素数的平方，
      #大于则判断是否整除该素数，等于则证明该数是非素数。
      #前俩者不成立，则该数小于素数平方证明该数为素数。
   
    while  $arr[j] * $arr[j] <=number
      return false  if  number  %  $arr[j] ==0
      j +=1
    end
    return true
 end

add_prime(50)
print  $arr.join(", "),"\n"          #转换成字符串输出

评论
njmzhang 2007-07-17
graying 写道
说优化谈不上，但是ruby写的确方便很多。
哪里看到过的例子，回忆了写的： 
(2..50).each{|n| s=true; (2..n-1).each{|f| (s=false; break;) if n%f==0 }; puts n if s}


(2..50).inject([]) { |s, e| (s.map { |x| e % x }).include?(0) ? s : s << e }
xangd 2007-07-16
50以内?
搞个对照表查一下最快乐 哈哈
roger 2007-07-16
判断素数最快还是费马小定理
graying 2007-07-14
说优化谈不上，但是ruby写的确方便很多。
哪里看到过的例子，回忆了写的： 
(2..50).each{|n| s=true; (2..n-1).each{|f| (s=false; break;) if n%f==0 }; puts n if s}
dennis_zane 2007-07-14
费马小定理来检测，对数级的增长阶
skyin 2007-07-13
还没有更高效率的？
yuhai.china 2007-07-13
求素数的标准算法是“筛法”，呵呵
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

您还没有登录，请登录后发表评论

laies
搜索本博客
最近加入圈子
存档
最新评论