程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++編程練習一-回文素數

C++編程練習一-回文素數

編輯：C++入門知識

Description
一個數如果從左往右讀和從右往左讀數字是相同的，則稱這個數是回文數，如121，1221，15651都是回文數。給定位數n，找出所有既是回文數又是素數的n位十進制數。（注：不考慮超過整型數范圍的情況）。
Input
位數n,其中1<=n<=9。
Output
第一行輸出滿足條件的素數個數。
第二行按照從小到大的順序輸出所有滿足條件的素數，兩個數之間用一個空格區分。
Sample Input
1
Sample Output
4
2 3 5 7
參考代碼
view plaincopy to clipboardprint?
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
using namespace std;
int result[5960];
int r_s = 0;
int digit[10];
int a,b;
int pm[10000];
int pm_size = 0;
void init();
class MyString:public string{
public:
    MyString(int n);
    bool isPlalindrome();
private:
    string ds;
};
MyString::MyString(int n){
    while(n){
        char ch = (n % 10) + '0';
        n /= 10;
        ds.push_back(ch);
    }
}
bool MyString::isPlalindrome(){
    int len = ds.length();
    int mid = len / 2;
    for(int i = 0;i < mid; ++ i){
        if(ds[i] != ds[len - i - 1]){
            return false;
        }
    }
    return true;
}
void work( int c )
{
    int p = ( c - 1 ) >> 1, i, j, s = 1, r, t1, t2;
    if ( c == 1 )
    {
        if ( a <= 2 && b >= 2 )
            result[r_s ++] = 2;
        if ( a <= 3 && b >= 3 )
            result[r_s ++] = 3;
        if ( a <= 5 && b >= 5 )
            result[r_s ++] = 5;
        if ( a <= 7 && b >= 7 )
            result[r_s ++] = 7;
        digit[c] = 4;
        return ;
    }
    for ( i = 0; i < p; i++ )
        s *= 10;
    for ( i = 1; i < 10; i += 2 )
    {
        for ( j = 0; j < s; j++ )
        {
            r = i * s + j;
            t1 = j / 10;
            t2 = p - 1;
            while ( t2 )
            {
            r = r * 10 + ( t1 % 10 );
            t1 /= 10;
            t2--;
            }
            r = r * 10 + i;
            if ( r < a )
            continue;
            if ( r > b ){
                return ;
            }
            MyString s(r);
            if(s.isPlalindrome()){
                bool bl = true;
                for(int p = 0;p < pm_size && pm[p] < r;++ p){
                    if(r % pm[p] == 0){
                        bl = false;
                        break;
                    }
                }
                if(bl){
                    result[r_s ++] = r;
                    digit[c] ++;
                }
            }
        }
    }
}

int main( )
{
    int i, p, c;
    a = 2; b = 1000000000;
    p = 1;
    c = 0;
    init();
    while ( p < a )
    {
        c++;
        p *= 10;
    }
    p /= 10;
    while ( p < b )
    {
        if ( c == 2 )
        {
            digit[c] = 1;
            result[r_s ++] = 11;
        }
        if ( c & 1 )
            work( c );
        c++;
        p *= 10;
    }
    int n,start,end;
    scanf("%d",&n);
    printf("%d\n",digit[n]);
    start = (int)pow(10.0,n-1);
    end = (int)pow(10.0,n);
    for(i = 0;i < r_s;++ i){
        if(result[i] >= start && result[i] <= end){
            printf("%d ",result[i]);
        }
    }
    printf("\n");
    return 0;
}
void init(){
    for(int p = 2;p <= 100000;++ p){
        bool bl = true;
        for(int k = 2;k <= sqrt(1.0 * p);++ k){
            if(p % k == 0){
                bl = false;
                break;
            }
        }
        if(bl){
            pm[pm_size ++] = p;
        }
    }
    for(int i = 0;i < 10;++ i){
        digit[i] = 0;
    }
}
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
using namespace std;
int result[5960];
int r_s = 0;
int digit[10];
int a,b;
int pm[10000];
int pm_size = 0;
void init();
class MyString:public string{
public:
MyString(int n);
bool isPlalindrome();
private:
string ds;
};
MyString::MyString(int n){
while(n){
  char ch = (n % 10) + '0';
  n /= 10;
  ds.push_back(ch);
}
}
bool MyString::isPlalindrome(){
int len = ds.length();
int mid = len / 2;
for(int i = 0;i < mid; ++ i){
  if(ds[i] != ds[len - i - 1]){
   return false;
  }
}
return true;
}
void work( int c )
{
    int p = ( c - 1 ) >> 1, i, j, s = 1, r, t1, t2;
    if ( c == 1 )
    {
  if ( a <= 2 && b >= 2 )
   result[r_s ++] = 2;
  if ( a <= 3 && b >= 3 )
   result[r_s ++] = 3;
  if ( a <= 5 && b >= 5 )
   result[r_s ++] = 5;
  if ( a <= 7 && b >= 7 )
   result[r_s ++] = 7;
  digit[c] = 4;
  return ;
    }
    for ( i = 0; i < p; i++ )
  s *= 10;
    for ( i = 1; i < 10; i += 2 )
    {
  for ( j = 0; j < s; j++ )
  {
   r = i * s + j;
   t1 = j / 10;
   t2 = p - 1;
   while ( t2 )
   {
   r = r * 10 + ( t1 % 10 );
   t1 /= 10;
   t2--;
   }
   r = r * 10 + i;
   if ( r < a )
   continue;
   if ( r > b ){
    return ;
   }
   MyString s(r);
   if(s.isPlalindrome()){
    bool bl = true;
    for(int p = 0;p < pm_size && pm[p] < r;++ p){
     if(r % pm[p] == 0){
      bl = false;
      break;
     }
    }
    if(bl){
     result[r_s ++] = r;
     digit[c] ++;
    }
   }
  }
    }
}

int main( )
{
    int i, p, c;
    a = 2; b = 1000000000;
    p = 1;
    c = 0;
init();
    while ( p < a )
    {
  c++;
  p *= 10;
    }
    p /= 10;
    while ( p < b )
    {
  if ( c == 2 )
  {
   digit[c] = 1;
   result[r_s ++] = 11;
  }
  if ( c & 1 )
   work( c );
  c++;
  p *= 10;
    }
int n,start,end;
scanf("%d",&n);
printf("%d\n",digit[n]);
start = (int)pow(10.0,n-1);
end = (int)pow(10.0,n);
for(i = 0;i < r_s;++ i){
  if(result[i] >= start && result[i] <= end){
   printf("%d ",result[i]);
  }
}
printf("\n");
    return 0;
}
void init(){
for(int p = 2;p <= 100000;++ p){
  bool bl = true;
  for(int k = 2;k <= sqrt(1.0 * p);++ k){
   if(p % k == 0){
    bl = false;
    break;
   }
  }
  if(bl){
   pm[pm_size ++] = p;
  }
}
for(int i = 0;i < 10;++ i){
  digit[i] = 0;
}
}