转自：http://blog.csdn.net/dinosoft/article/details/5829550 一般的线性筛法 首先先介绍一般的线性筛法求素数 void make_prime() { memset(prime, 1, sizeof(prime)); prime[0]=false; prime[1]=false; int N=31700; for (int i=2; i<N; i+&

线性筛法 上节课讲的是 Eratosthenes 筛法利用的原理是 任意整数 x 的倍数 2x，3x，... 等都不是质数 。 但是即便如此也会有重复标记的现象，例如12既会被2又会被3标记，在标记2的倍数时，\(12 = 6*2\)，在标记3的倍数时，\(1

首先有以下性质：(p 为素数) 1. （p）=p-1 2. 如果i mod p==0，那么( i*p )=p*( i ) 3. 若i mod p≠0，那么（i*p）=（i）*（p-1） 证明见http://blog.csdn.net/Lytning/article/det