可以直接试除判断,也可以直接筛完存到bool数组。
关键点1 素数定理:不超过x的素数的个数大概为π(x) = x/ln(x)个
例如x = 100 = 10^2 , 大概为100/ln(100) = 21 。实际上质数个数为25 【误差3~4】
例如x = 1000 = 10^3 , 大概为1000/ln(1000) = 144 , 实际为质数个数为 168 【误差23~24】
关键点2 不含前导0
比如62-> 6203 本应该符合条件,但因为加的是03 含有前导0,所以不符合,所以结果为另外一个素数6211
比如1 -> 11 -> 110 -> 1100 ~ 符合本题条件,虽然后面有0,但是加的是100所以 不含前导0,所以符合
关键点3 如何避免前导0?
例如62 -> 621【62 * 10】 -> 6210【62 * 100 + 100 / 10】;
C++ 代码
#include<iostream>
#define MAXN 10010
bool is_prime[MAXN];
void erato(int n){ //埃
for(int i = 2 ; i <= n ; i ++){
is_prime[i] = true;
}
for(int i = 2 ; i * i <= n ; i ++){
if(is_prime[i]){
for(int j = i * i ; j <= n ; j += i){
is_prime[j] = false;
}
}
}
}
int find(int x , int k){
for(int i = x * k + (k / 10) ; i <= (x + 1) * k - 1 ; i++){ //i < x * k
if(is_prime[i]) return i;
}
return find(x , k * 10);
}
int main(){
int n , x;
std::cin >> n;
erato(MAXN);
while(std::cin >> x){
printf("%d\n" , find(x , 10));
}
return 0;
}