NOI 3247:回文素数

题目

http://bailian.openjudge.cn/practice/3247/

思路

判断素数直接遍历根号因子,本题需要生成n位的回文数字同时需要知道以下性质
偶数位的回文数字都可以被11整除,只考虑基数位的回文数字,同时我采用的构造方法是遍历对称轴前方的数字,而后中间插入0-9,但实际上可以直接带着对称轴数字直接便利,只不过在生成回文数的时候提前除10

源码

//
//  3247.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//  Copyright © 2020 bytedance. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

bool isP(int n){
    int sq = sqrt(n)+1;
    for(int i = 2;i <= sq;++i){
        if(n%i==0)return false;
    }
    return true;
}
int main(){
    int n;
    cin >> n;
    if(n == 1){
        cout <<"4\n2 3 5 7";
    }else if(n==2)cout<<"1\n11";
    else if(n==4||n==6||n==8) cout<<"0";
    else{
        int len = n/2;
        int mn = pow(10,len-1);
        int mx = pow(10,len)-1;
        int cnt;
        vector<int> res;
        for(int i = mn;i <= mx;++i){
            vector<int> hui(10,i);
            int temp = i;
            for(int i = 0;i < 10;++i){
                hui[i]=hui[i]*10+i;

            }
            while(temp!=0){
                for(int i = 0;i < 10;++i){
                    hui[i]=hui[i]*10+temp%10;
                }
                temp/=10;
            }
//            cout<<i<<endl;
            for(int i = 0;i < 10;++i){
                if(isP(hui[i]))res.push_back(hui[i]);
//                cout << hui[i]<<" ";
            }
        }
        cout << res.size()<<endl;
                  for(int i = 0;i < res.size();++i){
                      cout <<res[i]<<" ";
                  }
    }
    return 0;
}
发布于 :NOI

发表评论

电子邮件地址不会被公开。 必填项已用*标注