• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            素數篩法

            Posted on 2010-03-12 14:04 rikisand 閱讀(1547) 評論(0)  編輯 收藏 引用 所屬分類: C/C++

            #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 缺陷:合數可能被多次篩掉,例如 30被2,3,5篩掉了3次 然后 線性篩法限定了 任何一個合數只被它的最小質因數篩掉一次,怎么做到這一點~~

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

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

            国产高清国内精品福利99久久 | 欧美粉嫩小泬久久久久久久| 久久久久国产精品| 国产日韩久久久精品影院首页| 久久精品无码一区二区三区| 国产精品欧美亚洲韩国日本久久| 一级做a爰片久久毛片毛片| 新狼窝色AV性久久久久久| 久久国产高清字幕中文| 亚洲?V乱码久久精品蜜桃| 久久精品亚洲日本波多野结衣 | 久久婷婷五月综合97色直播| 亚洲精品无码久久千人斩| 久久免费小视频| 国产精品久久久久久久人人看| 久久成人国产精品| 日韩久久久久中文字幕人妻| 99久久精品国产高清一区二区| 久久亚洲视频| 国产精品无码久久久久| 日本人妻丰满熟妇久久久久久| 久久无码人妻精品一区二区三区 | 亚洲AV成人无码久久精品老人| 久久精品国产福利国产琪琪| 久久久久久精品免费看SSS | 久久久久高潮综合影院| 99久久www免费人成精品| 久久久久久亚洲精品成人| 亚洲人AV永久一区二区三区久久| 久久综合丁香激情久久| 精品久久久久久无码专区| 久久久久青草线蕉综合超碰| 久久免费视频一区| 久久久综合香蕉尹人综合网| 亚洲国产精品久久| 国产精品久久久久影院嫩草| 久久99精品国产自在现线小黄鸭 | 狠狠色丁香久久婷婷综合五月| 久久国产劲爆AV内射—百度| 婷婷久久五月天| 2021国产精品久久精品|