亂八七糟的代碼

#include <iostream> 
#include <vector>
#include "time.h"
using namespace std; 
void sieve(int n){
    vector<bool> isprime(n,true);
    vector<int> prime;
    int cnt=0;
    for(int i=2;i<n;i++){
        if(isprime[i])cnt++,prime.push_back(i);
        for(int t=0;t<cnt&&i*prime[t]<n;t++){
            isprime[i*prime[t]]=false;
            if(i%prime[t]==0)break;
        }
    }
    /*for(int i=0;i<cnt;i++)
        cout<<prime[i]<<" ";*/
}
void oldseive(int n){
    vector<bool> isprime(n,true);
    vector<int> prime;
    for(int i=2;i<n;i++){
        if(isprime[i]){
            prime.push_back(i);
            for(int j=i*2;j<n;j+=i)
                isprime[j]=false;
        }
    }
    /*for(int i=0;i<prime.size();i++)
        cout<<prime[i]<<" ";*/
}
int main(){
    clock_t start,end;
    start = clock();
     sieve(2000000);
     //oldseive(2000000);
    end  = clock();
    double time = double(end-start)/CLOCKS_PER_SEC;
    cout<<endl<< time<<endl;
} 

線性篩法sieve 1.546s oldsieve 2.875s 快了將近一倍

old sieve 缺陷：合數(shù)可能被多次篩掉，例如 30被2，3，5篩掉了3次 然后 線性篩法限定了 任何一個合數(shù)只被它的最小質(zhì)因數(shù)篩掉一次，怎么做到這一點~~

if(i%prime[t]==0) break; 如果此時篩掉的合數(shù)從小到大找到第一個可以整除的質(zhì)數(shù)，那么顯然他找到了它的最小質(zhì)因數(shù)，此時我們停止搜索質(zhì)數(shù)表，因為后面的質(zhì)數(shù)比當(dāng)前的prime[t]要大，如果我們用prime[t+n]*i 篩掉了一個合數(shù)，這個合數(shù)必然可以表述成為 prime[t]*someK  *prime[t+n] 也就是說這個合數(shù)的最小質(zhì)因數(shù)也是prime[t],他應(yīng)該被 prime[t]篩掉-->當(dāng)程序運行到 someK*prime[t+n] 的時候~~~~

over--------------------------------------------------------------------