这里x,y <= 10 ^ 12和yx <= 10 ^ 6
我从左到右循环并检查每个数字是否为素数..当x和y有点像10 ^ 11和10 ^ 12 ..任何更快的方法时,此方法都很慢。我将所有素数存储到10 ^ 6 ..我可以使用它们在10 ^ 10-10 ^ 12之类的巨大值之间找到素数吗?
for(i=x;i<=y;i++)
{
num=i;
if(check(num))
{
res++;
}
}
我的支票功能
int check(long long int num)
{
long long int i;
if(num<=1)
return 0;
if(num==2)
return 1;
if(num%2==0)
return 0;
long long int sRoot = sqrt(num*1.0);
for(i=3; i<=sRoot; i+=2)
{
if(num%i==0)
return 0;
}
return 1;
}
使用Eratosthenes的分段筛。
即,使用一个比特集合来存储之间的数字x
和y
,由下式表示x
作为偏移和[0,YX)中的比特集。然后筛选(消除倍数)所有小于或等于的平方根的质数 y
。集合中保留的那些数字是质数。
随着y
在10 12你有一个素数筛出至多10 6,这将需要不到一个正确实施第二。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句