NOI-OJ 1.13 ID:11 回文素数

NOI-OJ 1.13 ID:11 回文素数

总时间限制: 5000ms 内存限制: 65536kB
描述
一个数如果从左往右读和从右往左读数字是相同的，则称这个数是回文数，如121，1221，15651都是回文数。给定位数n，找出所有既是回文数又是素数的n位十进制数。（注：不考虑超过整型数范围的情况）。

输入
位数n,其中1<=n<=9。
输出
第一行输出满足条件的素数个数。
第二行按照从小到大的顺序输出所有满足条件的素数，两个数之间用一个空格区分。
样例输入

1

样例输出

4
2 3 5 7

关键点

1. 分析过程

• 回文素数的特点是偶数位数的数不是回文素数（特例：11）
• 先求出回文数再求出素数更快，计算量少。
• 镜像制造回文数，数据小。

1. 步骤

• 遍历n/2位的数，生成回文数
• 判断是否为素数，存储数据

代码

int isPrime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)
            return 0;
    }
    return 1;
}

vector<int> v; // 存储回文素数

int main(){
    int n;
    scanf("%d", &n);
    if(n==1){ // 1位数
        cout << "4\n2 3 5 7";
    }else if(n==2){ // 2位数
        cout << "1\n11";
    }else if(n==3||n==5||n==7||n==9){// 奇数位数
        double d = pow(10, (n-1)/2); // 得到n位数对称轴前面的数（包括对称轴）
        int i = (int)d; // C++中直接转int，会舍弃小数点后面的数，所以用了两步。
        for(i;i<d*10;i++){ // 遍历n位数
            int sum=i;
            int ii=i;
            ii/=10;
            while(ii!=0){ // sum 生成的回文数
                sum = sum*10+ii%10;
                ii/=10;
            }

            if(sum%2!=0){ // sum的末位不是偶数，同时也表明首位不是偶数
                if(isPrime(sum)){ // 是否为素数
                    v.push_back(sum);
                }
            }
        }
        printf("%d\n", (int)v.size());
        for(int i=0;i<(int)v.size();i++){
            printf("%d ",v[i]);
        }
    }else{ // 偶数位数是不存在回文质数的，除了11。
        printf("0");
    }
    return 0;
}