P1217 [USACO1.5] 回文质数 Prime Palindromes

时间限制: 1.00s    内存限制: 125.00MB

题目描述

因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)（一亿）间的所有回文质数。

输入格式

第一行输入两个正整数 a 和 b。

输出格式

输出一个回文质数的列表，一行一个。

#include <iostream>
#include <vector>
using namespace std;
bool prime(int num){
    if(num%2==0){
        return false;
    }
    for(int i = 3;i*i<=num;i=i+2){
        if(num%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int a,b;
    cin>>a>>b;
    vector<int> prime_palindrome{5,7,11};
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           int palindrome = 100*d1 + 10*d2 + d1;
           if(prime(palindrome)){
               prime_palindrome.push_back(palindrome);
           }
       }
    }
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           int palindrome = 1000*d1 + 100*d2 + 10*d2 + d1;
           if(prime(palindrome)){
               prime_palindrome.push_back(palindrome);
           }
       }
    }
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           for(int d3 = 0;d3 <= 9;d3++){
               int palindrome = 10000*d1 + 1000*d2 + 100*d3 + 10*d2 +d1;
               if(prime(palindrome)){
                   prime_palindrome.push_back(palindrome);
               }
           }
       }
    }
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           for(int d3 = 0;d3 <= 9;d3++){
               int palindrome = 100000*d1 + 10000*d2 + 1000*d3 + 100*d3 + 10*d2 +d1;
               if(prime(palindrome)){
                   prime_palindrome.push_back(palindrome);
               }
           }
       }
    }
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           for(int d3 = 0;d3 <= 9;d3++){
               for(int d4 = 0;d4 <= 9;d4++){
                   int palindrome = 1000000*d1 + 100000*d2 + 10000*d3 + 1000*d4 + 100*d3 + 10*d2 + d1;
                   if(prime(palindrome)){
                       prime_palindrome.push_back(palindrome);
                   }
               }
           }
        }
    }
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           for(int d3 = 0;d3 <= 9;d3++){
               for(int d4 = 0;d4 <= 9;d4++){
                   int palindrome = 10000000*d1 + 1000000*d2 + 100000*d3 + 10000*d4 + 1000*d4 + 100*d3 + 10*d2 + d1;
                   if(prime(palindrome)){
                       prime_palindrome.push_back(palindrome);
                   }
               }
           }
        }
    }
    for(int d1 = 1 ;d1 <= 9;d1++){
       for(int d2 = 0;d2 <= 9;d2++){
           for(int d3 = 0;d3 <= 9;d3++){
               for(int d4 = 0;d4 <= 9;d4++){
                   for(int d5 = 0;d5 <= 9;d5++){
                       int palindrome = 100000000*d1 + 10000000*d2 + 1000000*d3 + 100000*d4 + 10000*d5 + 1000*d4 + 100*d3 + 10*d2 + d1;
                       if(prime(palindrome)){
                           prime_palindrome.push_back(palindrome);
                       }
                   }
               }
           }
        }
    }
    for(int i = 0;i < prime_palindrome.size();i++){
        if(prime_palindrome[i]>=a&&prime_palindrome[i]<=b){
            cout<<prime_palindrome[i]<<endl;
        }
        else if(prime_palindrome[i]>b){
            break;
        }
    }
    return 0;
}