今天在博文C語(yǔ)言初學(xué)者代碼中的常見(jiàn)錯(cuò)誤與瑕疵(5)看了一個(gè)關(guān)于素?cái)?shù)的算法題，如下：
素?cái)?shù)
在世博園某信息通信館中，游客可利用手機(jī)等終端參與互動(dòng)小游戲，與虛擬人物Kr. Kong 進(jìn)行猜數(shù)比賽。
當(dāng)屏幕出現(xiàn)一個(gè)整數(shù)X時(shí)，若你能比Kr. Kong更快的發(fā)出最接近它的素?cái)?shù)答案，你將會(huì)獲得一個(gè)意想不到的禮物。
例如：當(dāng)屏幕出現(xiàn)22時(shí)，你的回答應(yīng)是23；當(dāng)屏幕出現(xiàn)8時(shí)，你的回答應(yīng)是7；
若X本身是素?cái)?shù)，則回答X;若最接近X的素?cái)?shù)有兩個(gè)時(shí)，則回答大于它的素?cái)?shù)。
輸入：第一行：N 要競(jìng)猜的整數(shù)個(gè)數(shù)
接下來(lái)有N行，每行有一個(gè)正整數(shù)X
輸出：輸出有N行，每行是對(duì)應(yīng)X的最接近它的素?cái)?shù)
樣例：輸入
4
22
5
18
8
輸出
23
5
19
7
看到這個(gè)算法題我們首先要做的就是實(shí)現(xiàn)一個(gè)函數(shù)，來(lái)求出一個(gè)數(shù)是否是質(zhì)數(shù)。下面我們來(lái)簡(jiǎn)單的實(shí)現(xiàn)一下：
bool isPrime(int num){ if(num < 2) return false; for(int i=2; i*i<num; ++i){ if(num % i == 0) return false; } return true;}
由于這個(gè)函數(shù)在算法中會(huì)多次用到，我們用下面的測(cè)試來(lái)查看這個(gè)基本函數(shù)的效率
void test(){ clock_t start = clock(); for(int i=1; i <= 100000; ++i){ isPrime(1000000007); } clock_t end = clock(); cout << endl << static_cast<double>(end - start)/CLOCKS_PER_SEC << endl;}
運(yùn)行，得到結(jié)果12.158
因?yàn)槠陂g我們可能會(huì)進(jìn)行重復(fù)的計(jì)算，對(duì)這個(gè)問(wèn)題我一開(kāi)始想到的解決方法就是建立一個(gè)質(zhì)數(shù)表，我們可以直接通過(guò)查找表來(lái)快速的確定一個(gè)數(shù)是否是質(zhì)數(shù)。當(dāng)要判斷的數(shù)很大時(shí)，需要占用很大的空間來(lái)建表，為了節(jié)約空間，我將每一位都充分用上了。
#define GETNUM(x) psum[((x)>>3)]&(1<<(((x)&7)-1))#define SETNUM(x) psum[((x)>>3)] &= (~(1<<(((x)&7)-1)))bool isPrime(int num){ if(num < 2) return false; int size = (num>>3)+1; unsigned char *psum = new unsigned char[size]; memset(psum, 0xFF, size); for(int i=2; i*i<num; ++i){ if(GETNUM(i)){ for(int j=i<<1; j<=num; j+=i){ SETNUM(j); } } } bool result = GETNUM(num); delete [] psum; return result;}
因?yàn)橘|(zhì)數(shù)表建立起來(lái)以后，之后的判斷直接取值就行了，所以我們就不做循環(huán)了，直接看它運(yùn)行一次的時(shí)間，竟然用了29.853！耗時(shí)太長(zhǎng)了，建這個(gè)表的時(shí)間可以進(jìn)行20萬(wàn)次試除法判斷了。
在經(jīng)過(guò)一定的分析后，我將這個(gè)過(guò)程進(jìn)行了一下優(yōu)化
#define GETNUM(x) psum[((x)>>3)]&(1<<(((x)&7)-1))#define SETNUM(x) psum[((x)>>3)] &= (~(1<<(((x)&7)-1)))bool isPrime2(int num){ if(num < 2) return false; int size = (num>>3)+1; unsigned char *psum = new unsigned char[size]; memset(psum, 0xFF, size); for(int j=4; j<num; j+=2){ SETNUM(j); } for(int i=3; i*i<num; ++i){ if(GETNUM(i)){ int step = i<<1; for(int j=i*i; j<=num; j+=step){ SETNUM(j); } } } bool result = GETNUM(num); delete [] psum; return result;}
上面的優(yōu)化，我先是直接將2的倍數(shù)都淘汰掉，接著，基于在進(jìn)行i的倍數(shù)判斷時(shí)，所有i的i-1以下的倍數(shù)都已經(jīng)被淘汰掉了這一點(diǎn)，直接從i的平方開(kāi)始淘汰，而且基于偶數(shù)倍能被2整除這一點(diǎn)，將步長(zhǎng)調(diào)整為i*2.
經(jīng)過(guò)優(yōu)化，時(shí)間縮短為16.429，可是這個(gè)結(jié)果明顯是不能讓人滿意滴。。。
這時(shí)我參看了一下博文一個(gè)超復(fù)雜的間接遞歸——C語(yǔ)言初學(xué)者代碼中的常見(jiàn)錯(cuò)誤與瑕疵(6)，發(fā)現(xiàn)只是計(jì)算部分質(zhì)數(shù)表，再利用質(zhì)數(shù)表來(lái)加快質(zhì)數(shù)的試除法這個(gè)方案很有可行性，于是趕緊行動(dòng)。先進(jìn)行預(yù)算，再進(jìn)行試除法判斷質(zhì)數(shù)。
改進(jìn)的結(jié)果是令人振奮滴，時(shí)間縮短為0.021.
解決了素?cái)?shù)判斷問(wèn)題，得到想要的算法就很容易了
void precalc(int size, int * primes, int &pnum){ bool *psum = new bool[size+1]; for(int j=4; j<=size; j+=2){ psum[j] = false; } memset(primes, 0, size * sizeof(int)); primes[0] = 2; pnum = 1; int i=3; for(; i*i<=size; ++i){ if(psum[i]){ primes[pnum] = i; ++pnum; int step = i<<1; for(int j=i*i; j<=size; j+=step){ psum[j] = false; } } } for(;i<=size; ++i){ if(psum[i]){ primes[pnum] = i; ++pnum; } } delete [] psum;}bool isPrime5(int num, const int * primes, int pnum){ for(int i=0; i<pnum && primes[i]*primes[i] < num; ++i){ if(num % primes[i] == 0) return false; } return true;}int get_nearest(int num, const int * primes, int pnum){ if(isPrime5(num, primes, pnum)) return num; int len; if(num % 2 == 0){ len = 1; } else{ len = 2; } while(true){ if(isPrime5(num+len, primes, pnum)) return num + len; if(isPrime5(num-len, primes, pnum)) return num - len; len += 2; }} int _tmain(int argc, _TCHAR* argv[]){ cout<<"請(qǐng)輸入數(shù)據(jù)"<<endl; int count; cin>>count; int *data = new int[count]; //最大的一個(gè)數(shù) int maxnum = 0; for(int i=0; i<count; i++){ cin>>data[i]; if(maxnum < data[i]){ maxnum = data[i]; } } int size = static_cast<int>(sqrt(static_cast<double>(maxnum))); int *primes = new int[size]; int pnum; precalc(size, primes, pnum); for(int i=0; i<count; i++){ cout<<get_nearest(data[i], primes, pnum)<<endl; } delete [] primes; delete [] data; cin.get(); return 0;}
聯(lián)系客服
