在做挑战里面的题目，关于质数，不知道怎么表示才比较高效

rosynirvana · 发表于 2013-6-3 20:23:10

挑战里能用到两种
1.试除
对于一个整数n，试验2，3到√n之间的所有奇数能否整除n

2.筛法
初始化一个数组a[1] =0 a[2] =2 ... a[n] = n
然后查找数组中第一个非零项i，存储起来，将数组中所有a的倍数设为0
一直循环下去，直到你找到的i > √n
将之前存储起来的数，和a中现有的非零项合并，就是从2-n之间的所有质数

Teddy · 发表于 2013-6-3 20:58:08

我不知道你现在的水平，最次的是循环试除，一般情况下用素数筛子（位存储），当然要是更高级一点，你可以用动态素数表，或者拉宾米勒测试（当然这是概率判定）

吐槽有理 · 发表于 2013-6-3 22:00:39

我的话因为水平不高，用循环试除做一个鉴别素数的函数来做的

在做挑战里面的题目，关于质数，不知道怎么表示才比较高效

最佳答案