HDU 1431 素数回文 - c++编程基础

有人问我这个问题。

个人感觉暴搜会TLE O(n*sqrt(n))。n=100000000；（判断素数用2~sqrt(n)+1 去除）

还是枚举好了。枚举 1~10000，把他每一位存下来，回文数已知 left ，求 right ，然后组合起来。

例如 1 ，判断 11 是否素数。

例如 10 ，判断 101 是否素数，判断 1001 是否素数。

这样复杂度就是 O(n^2)。开始我 bool pa[100000000] 准备用标记来确定。结果MLE。

然后算了一下总共有多少个数，最多 781 个。 int pa[1000] 就可以装下了。

G++ 15ms

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i=a;i
              
               =b;i--) #define pb push_back #define mp make_pair #define ft first #define sd second #define sf scanf #define pf printf #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() #define acfun std::ios::sync_with_stdio(false) #define SIZE 100000000 +1 using namespace std; int pa[1000]; int cot; bool prime(int n) { FOR(i,2,sqrt(n)+2) if(n%i==0)return 0; return 1; } void PA() { cot=0; pa[cot++]=2; pa[cot++]=3; pa[cot++]=5; pa[cot++]=7; FOR(i,1,10000) { int num[5]; int len=0; int m=i; while(m) { int tmp=m%10; num[len++]=tmp; m/=10; } int ans=i; if(len>1) { FOR(r,1,len) ans=ans*10+num[r]; if(prime(ans)) pa[cot++]=ans; } ans=i; FOR(r,0,len) ans=ans*10+num[r]; if(prime(ans)) pa[cot++]=ans; } } int main() { PA(); int a,b; while(~sf("%d%d",&a,&b)) { FOR(i,0,cot) if(pa[i]>=a&&pa[i]<=b)pf("%d\n",pa[i]); pf("\n"); } }