6N+-1法
- 算法描述:任何一个自然数,总可以表示成为如下的形式之一: 6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,
所有的素数都可以表示成6N±1的形式(N为自然数)。 根据上述分析,我们可以构造另一面筛子,只对形如6
N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0-1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。 - 性能测试:num=50000,时间:50ms
- 总结:此算法,其实也是一种筛选算法,只是筛子更细,能够将整数中大约2/3的数筛选出去。所以效率很高
【浅谈数论(二)进阶素数筛法】c++代码如下:
Compile OK
Status=AcceptedTotTime=0msMaxMemory=0kbScore=0(来自XJOI的测评)
#include
#include
using namespace std;
int n,m;
void make_prime()
{
for(int i=n/6;
;
i++){
for(int j=0;
j<=1;
j++){
int tmp=2*(3*i+j)-1;
if(tmpm)return;
bool flag=true;
for(int k=2;
k*k<=tmp;
k++)
if(!(tmp%k)){
flag=false;
break;
}
if(flag)printf("%d ",tmp);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
make_prime();
return 0;
}
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope(分治+NTT)
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally