求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"          #转换成字符串输出

评论

7 楼 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 }

6 楼 xangd 2007-07-16  

50以内?
搞个对照表查一下最快乐 哈哈

5 楼 roger 2007-07-16  

判断素数最快还是费马小定理

4 楼 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}

3 楼 dennis_zane 2007-07-14  

费马小定理来检测，对数级的增长阶

2 楼 skyin 2007-07-13  

还没有更高效率的？

1 楼 yuhai.china 2007-07-13  

求素数的标准算法是“筛法”，呵呵