浅谈数论（二）进阶素数筛法数论

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的数筛选出去。所以效率很高

（摘录自http://heisedeyueya.iteye.com/）
【浅谈数论（二）进阶素数筛法】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; }