1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 void get_prime(vector<int>&prime,int upper_bound){ 5 vector<bool> Is_prime (upper_bound+1,true); 6 if(upper_bound < 2)return; 7 for(int i = 2; i <= upper_bound; i++){ 8 if(Is_prime[i]){ 9 prime.push_back(i); 10 for(int j = i+i; j <= upper_bound; j+= i){ 11 Is_prime[j] = false; 12 } 13 } 14 } 15 return; 16 } 17 int main(){ 18 vector<int> prime; 19 get_prime(prime, 1000000); //O(nloglogn); 20 for(vector<int> :: iterator it = prime.begin(); it not_eq prime.end(); it++){ 21 cout<<*it<<" "; 22 } 23 return 0; 24 }
引理1: 任何大于1的数一定可以写成若干个素数的乘积，且一旦将每一个素因子从小到大排列，这个排列是固定的。
引理2: 任何一个合数，一定可以被一个小于或等于根号n的素数整除。由于n是合数，故n = x*y，此时，x、y必有一个数小于或等于n（反证法易证），不妨设x <= 根号n。 那么对于x，依据引理1，x一定可以被某一个素数整除，故得证n可被某个素数整除。
证明筛法：用反证法：假设筛法会保留某一个合数n，那么说明这个合数没有被2～n的所有素数整除，与引理2矛盾。假设有一个素数被筛除，说明素数被一个除自身以外的、大于等于2的数整除，显然错误。故得证筛法正确。
算法演示图：
原文：https://www.cnblogs.com/popodynasty/p/12122652.html