一定要是高效的。循环次数越少越好。。
在线急等。。。多谢
利用先前已得到的素数表判定
以下是C++代码,自己改成JAVA的吧
直接调用initprime();50000以内的素数就保存在plist中了,个数为pcount;
适当修改plist数组的大小,以及50000这个上界,可以求更大范围的素数
这个复杂度我不会算 感觉要远小于O(NlogN)的,效率应该还可以
int plist[10000],pcount=0;
int prime(int n)
{
int i;
if((n!=2 && !(n%2)) || (n!=3 && !(n%3)) || (n!=5 && !(n%5)) || (n!=7 && !(n%7))
return 0;
for(i=0;plist[i]*plist[i]<=n;++i)
if(!(n%plist[i]))
return 0;
return n>1;
}
void initprime()
{
int i;
for(plist[pcount++]=2,i=3;i<50000;++i)
if(prime(i))
plist[pcount++]=i;
}
[此贴子已经被作者于2007-9-17 8:36:02编辑过]