xan walking & thinking

学习实践

BlogJava

管理

28 Posts :: 0 Stories :: 2 Comments :: 0 Trackbacks

一个求素数的算法（不懂）

def is_prime?(number)   #定义方法判断数number是否是素数
    j=2                                #数组下标
    while $arr[j] * $arr[j] <=number     #$arr[] 是一个数组，记录number之前的素数，搞不懂为什么可以这么写
      return false if number % $arr[j] ==0
      j +=1
    end
    return true
end

土人求教

posted on 2008-05-05 15:18 xan 阅读(68) 评论(2) 编辑收藏

Feedback

# re: 一个求素数的算法（不懂） 2008-05-08 12:17 郑晖

while $arr[j] * $arr[j] <=number （若number有一大于其平方根的因子，则必有小于其平方根的因子，在此之前必已返回false。故此当$arr[j] * $arr[j] >number时循环即可中止）

return false if number % $arr[j] ==0（如果number能被arr[j]整除，当然不是素数，故返回false）回复更多评论

# re: 一个求素数的算法（不懂） 2008-05-08 14:10 xan

@郑晖
$arr[] 数组存储的是小于number的素数集合
return false if number % $arr[j] ==0 $arr[j] 是小于number的某一个素数
这就是我搞不懂的，实际上，我们熟知的判断素数方法是：
for(i=0; i<sqrt(number); i++) // 或者 i*i < number
{
if(number%i == 0) return false;
}
return true;

你说的是这个吧
回复更多评论