求素数最优算法
bool isss(int i)
{
int j;
for(j=2;j <=i/2;j++)
{
if (i%j==0)
{
return false;
}
}
return true;
}
我是这样求的
是的话 返回TRUE 不是的 返回 FALSE
请大家给出最优的求素数算法~！
[解决办法]
如果你所谓的最优，
是指的 for(j=2;j <=i/2;j++) 这里循环次数最少，
可以这样：
int tmp=sqrt(i)+1;
for(j=2;j <=tmp;j++) //开方+1 比 i/2 +1 要更少一些 ～
[解决办法]
我有一个比较优化的,因为判断一个数n是不是素数要从2除到n,而实际上,当除到根号n的时候,如果除不尽,就说明这个数已经没必要再去除根号n到n之间的数了,代码如下:
void main()
{
int n,i,k;
for(n=1;n <10;n++) //1-10间的素数
{
k=(int)sqrt(n);
for(i=2;i <=k;i++)
{
if(n%i==0) //只要除尽一次,就不是素数
{
cout < <n < < " is not " < <endl;
break;
}
}
if(i> k) //除到k一直没除尽,是素数
cout < <n < < " is " < <endl;
}
}
[解决办法]
随机算法里面有讲，用蒙特卡罗算法，在输入素数的情况下一定能得出正确判断，输入非素数情况有小概率出错，时间可以从O(n^1/2) -> O(logn * logn)
[解决办法]
有一个比较快的算法,利用所谓 "伪素数 "概念.
由Fermat定理我们知道, 当p为不等于２的素数时，
2 ** (p-1) = 1 (mod p)
反过来，如果一个数p满足上式，我们称之为 "伪素数 ". 因此所有的素数都是伪素数，但伪素数不一定是素数．有趣的是，统计后发现绝大多数伪素数确实是素数，呵呵．
因此，在判定一个数n是否为素数时，我们可以用上式很简单地先判断它是否是伪素数()，如果不是，它肯定是合数．如果是的话，再用上面所说的从２到sqr(n)循环取余判断它是否是真正的素数．看起来这样算法反而复杂了，但实际上因为绝大多数合数过不了第一关，它比一开始就循环比较要快．特别是当n很大的时候其优势更明显．
[解决办法]
你这是判断一个数是否是素数？然后呢？
如果是求1到10000之间的所有素数，推荐那个相除，从2开始除，除尽的都改成-1。
[解决办法]
Eratosthenes筛选法，思想非常简单明了，具体细节楼主可以自己去查。
[解决办法]
搞算法的关键是从大局上搞明白思想，看代码恐怕...
[解决办法]
int tmp=sqrt(i)+1;
for(j=3;j <=tmp;j+=2) //开方+1 比 i/2 +1 要更少一些 ～
{
if （0 == i % j）
return 0；
}
return 1；
[解决办法]
似乎有个筛法的，不过也记不清了
[解决办法]
这个问题要看你的算法的运行环境了，如果脱离工程上的运用去单单讨论哪个更好觉得意义不大。你具体的该函数的执行情况，多次/单次/输入范围/空间限制
推荐先用随机算法，然后再用开平方的方法，这样求的话的平均效率最高
[解决办法]
可能是 int 的范围问题
[解决办法]
拉宾米勒 算法
[解决办法]
bool PrimeMoteKaloTest(int a)
{
time_t time;
srand(time(&time));
while(1){
if (a%(rand()%a);==0)
return false;
else
return true;
}
}
[解决办法]
"int tmp=sqrt(i)+1;
for(j=2;j <=tmp;j++) //开方+1 比 i/2 +1 要更少一些 ～ "
这段代码的循环次数为sqrt(i)次，仍然有优化的余地；
首先，如果一个数能够被4，6，8等偶数整数，那么一定能够被2整除，因此没有必要对偶数试除，可改为以下代码，在最坏情况下，这个代码可提速一倍。
"int tmp=sqrt(i)+1;
if (i % 2==0)
return false;
for(j=3;j <=tmp;j+=2) //开方+1 比 i/2 +1 要更少一些 ～ "
{
if (i % j==0)
return false;
}
return true;
更进一步，没有必要对所有奇数进行试除，只需对所有sqrt(i)以内的所有质数试除就可以了，为此，需要事先建立一个sqrt(i)以内的质数表。
如果sqrt(i)很大，建议一个很大的质数表有困难的话，可以仅对2，3，5，7 以及 30K-1,30K+1,30K-7,30K+7,30K-11,30K+11, 30K-13,30K+13 这样的数进行试除，前面的方法对所有奇数试除需要 0.5*sqrt(i)次除法， 而这个需要0.266*sqrt(i)次除法，速度提高近1倍。
以上算法的复杂度为大抵为sqrt(i),如果想进一步提高速度，就需要使用米勒测试算法，这个算法不保证绝对正确，但可保证在%99.999999的情况下正确，每做一次米勒测试，误判的概率降为以前的1/4，欲得到更高的精度，只需做更多次米勒测试就可以了。在使用使用过程中，这个算法被大量使用，如RSA加密算法。
如果需要找出某一区间的的所有质数，如10000-20000，或1-1000000000，最好的算法应该是爱氏筛法，这个算法有很多改进版本，具体代码和算法可以上网查查。