素數
在世博園某信息通信館中，游客可利用手機等終端參與互動小游戲，與虛擬人物Kr. Kong 進行猜數比賽。
當屏幕出現一個整數X時，若你能比Kr. Kong更快的發出最接近它的素數答案，你將會獲得一個意想不到的禮物。
例如：當屏幕出現22時，你的回答應是23；當屏幕出現8時，你的回答應是7；
若X本身是素數，則回答X;若最接近X的素數有兩個時，則回答大於它的素數。
輸入：第一行：N 要競猜的整數個數
接下來有N行，每行有一個正整數X
輸出：輸出有N行，每行是對應X的最接近它的素數
樣例：輸入
4
22
5
18
8
輸出
23
5
19
7
看到這個算法題我們首先要做的就是實現一個函數，來求出一個數是否是質數。下面我們來簡單的實現一下：
復制代碼
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;
}
復制代碼
由於這個函數在算法中會多次用到，我們用下面的測試來查看這個基本函數的效率
復制代碼
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;
}
復制代碼
運行，得到結果12.158
因為期間我們可能會進行重復的計算，對這個問題我一開始想到的解決方法就是建立一個質數表，我們可以直接通過查找表來快速的確定一個數是否是質數。當要判斷的數很大時，需要占用很大的空間來建表，為了節約空間，我將每一位都充分用上了。
復制代碼
#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;
}
復制代碼
因為質數表建立起來以後，之後的判斷直接取值就行了，所以我們就不做循環了，直接看它運行一次的時間，竟然用了29.853！耗時太長了，建這個表的時間可以進行20萬次試除法判斷了。
在經過一定的分析後，我將這個過程進行了一下優化
復制代碼
#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;
}
復制代碼
上面的優化，我先是直接將2的倍數都淘汰掉，接著，基於在進行i的倍數判斷時，所有i的i-1以下的倍數都已經被淘汰掉了這一點，直接從i的平方開始淘汰，而且基於偶數倍能被2整除這一點，將步長調整為i*2.
經過優化，時間縮短為16.429，可是這個結果明顯是不能讓人滿意滴。。。
這時我參看了一下博文一個超復雜的間接遞歸——C語言初學者代碼中的常見錯誤與瑕疵(6)，發現只是計算部分質數表，再利用質數表來加快質數的試除法這個方案很有可行性，於是趕緊行動。先進行預算，再進行試除法判斷質數。
View Code
改進的結果是令人振奮滴，時間縮短為0.021.
解決了素數判斷問題，得到想要的算法就很容易了
復制代碼
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<<"請輸入數據"<<endl;
int count;
cin>>count;
int *data = new int[count];
//最大的一個數
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;
}
