算法OJ—回文質數

回文質數

時限：1000ms 記憶體限制：10000K 總時限：3000ms

描述：

因為151既是一個質數又是一個回文數(從左到右和從右到左看是一樣的)，是以151是回文質數．

寫一個程式來找出範圍[a,b](5<=a<b<=100,000,000)間的所有回文質數．

輸入：

第一行　兩個整數：a和b．

輸出：

輸出一個回文質數的清單，一行一個．

輸入樣例：

5 500

輸出樣例：

5

7

11

101

131

151

181

191

313

353

373

383

本題我做了較長的時間，判斷回文質數很簡單即isPrime（）；isSyS（）；兩個if語句嵌套即可實作，但是送出後發現時間複雜較高，故思考因為判斷素數的複雜度較高，應該先判斷回文再判斷素數，并且對于回文的判斷使用數組存儲各位數字然後在進行對比也較為備援，想到回文數正反值相同，是以更改代碼如下：

#include<iostream>
#include<math.h>
using namespace std;

bool isPrime(int val){
    int q;
    for(q = 2; q <= sqrt(val); q++){
        if(val % q == 0){
            return false;
        }
    }
    if(q > sqrt(val)){
        return true;
    }
}

bool isSyS(int val){
    int a[11];
    int i = 0;
    int reverseVal = 0;
    int valrecord = val;
    while(true){
        reverseVal = reverseVal*10 + valrecord%10;
        valrecord = valrecord/10;
        if(valrecord < 1){
            break;
        }
    }
    if(reverseVal == val){
        return true;
    }else{
        return false;
    }
}

int main(){
    int a, b;
    cin >> a >> b;
    int i;
    for(i = a; i < b; i++){
        if(isSyS(i)){
            if(isPrime(i)){
                cout << i << endl;
            }
        }
    }
}
           

但是送出發現還是不能滿足時間複雜度要求，重新審題發現[a,b](5<=a<b<=100,000,000)區間上億次，如果進行窮舉操作則要執行百萬次的素數判斷，顯然時間複雜度很高。

通過在網絡檢索回文素數的性質，得知4位、6位、8位的回文數都不是素數。由此可以剔除一部分資料，在兩位數之内隻有三個回文素數，是以三位數以内的素數通過打表來進行計算，其他的按照數位，先生成回文數再進行素數的判斷；代碼如下:

#include<iostream>
#include<math.h>
using namespace std;

bool isPrime(int val){
    int q;
    for(q = 2; q <= sqrt(val); q++){
        if(val % q == 0){
            return false;
        }
    }
    if(q > sqrt(val)){
        return true;
    }
}

int getlength(int border){
    int m = 1, k = border;
    while(k > 9){
        k /= 10;
        m++;
    }
    return m;
}

int main(){
    int a, b;
    cin >> a >> b;
    int p, q;
    p = getlength(a);
    q = getlength(b);
    if(p <= 1 && q >=1){//一位
        if(a <= 5 && b>=5){
            cout << 5 << endl;
        }
        if(a <= 7 && b >= 7){
            cout << 7 << endl;
        }
    }

    if(p <= 2 && q >=2){//二位
        if(a <= 11 && b >= 11){
            cout << 11 << endl;
        }
    }

    if(p <= 3 && q >= 3){//三位
        int x,y;
        int temp;
        for(x = 1; x <= 9; x += 2){
            for(y = 0; y <= 9; y++){
                temp = x*100 + y*10 + x;
                if(temp >= a && temp <= b){
                    if(isPrime(temp)){
                        cout<<temp<<endl;
                    }
                }
            }
        }
    }

    if(p <= 5 && q >= 5){//五位
        int x,y,z;
        int temp;
        for(x = 1; x <= 9; x += 2){
            for(y = 0; y <= 9; y++){
                for(z = 0; z <= 9; z++){
                    temp = x*10000 + y*1000+ z*100 + y*10 +x;
                    if(temp >= a && temp <= b){
                        if(isPrime(temp)){
                            cout<<temp<<endl;
                        }
                    }
                }
            }
        }
    }

     if(p <= 7 && q >= 7){//七位
        int x,y,z,t;
        int temp;
        for(x = 1; x <= 9; x += 2){
            for(y = 0; y <= 9; y++){
                for(z = 0; z <= 9; z++){
                    for(t = 0; t <= 9; t++){
                        temp = x*1000000 + y*100000 + z*10000 + t*1000 + z*100 + y*10 + x;
                        if(temp >= a && temp <= b){
                            if(isPrime(temp)){
                                cout<<temp<<endl;
                            }
                        }
                    }
                }
            }
        }
    }





}