usaco Prime Palindromes

xiaoxiao2021-02-28  29

题意:给a,b。找出a - 》 b 范围内又是回文串又是素数的数。

看了看别人的博客,偶数个数组成的回文串一定不是素数。还有,开头是偶数的数,也不是,这个很容易想到。求素数的时候用到了唯一分解定理

算术基本定理可表述为:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan,这里P1<P2<P3......<Pn均为质数,其中指数ai是正整数。

所以我们只需要求到一个数n的sqrt(n)的素数,就可以利用这些素数判断n是否为素数。因为,如果2 - 》sqrt(n)没有n的因子,那么大于sqrt(n)是不可能出现两个因子的,所以只能是素数。

/** ID: DickensTone TASK: pprime LANG:C++ **/ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 10000 + 5; int palind[maxn]; int prime[maxn]; bool vis[maxn]; int cnt, p; void creat_prime() { p = 0; memset(vis, 0, sizeof(vis)); for(int i = 2; i < maxn; i++) { if(!vis[i]) { prime[p++] = i; int t = i; while(t < maxn) { vis[t] = 1; t = t * i; } } } } bool is_prime(int n) { for(int i = 0; i < p && prime[i] < n; i++) { if(n % prime[i] == 0) return false; } return true; } void creat_palind() { cnt = 0; for(int i = 2; i <= 11; i++) if(is_prime(i)) palind[cnt++] = i; for(int i = 1; i <= 9; i += 2)//3 { for(int j = 0; j <= 9; j++) { int t = i * 100 + j*10 + i; if(is_prime(t)) palind[cnt++] = t; } } for(int i = 1; i <= 9; i += 2)//5 for(int j = 0; j <= 9; j++) for(int k = 0; k <= 9; k++) { int t = i * 10000 + j * 1000 + k * 100 + j * 10 + i; if(is_prime(t)) palind[cnt++] = t; } for(int i = 1; i <= 9; i += 2)//7 for(int j = 0; j <= 9; j++) for(int k = 0; k <= 9; k++) for(int l = 0; l <= 9; l++) { int t = i * 1000000 + j * 100000 + k * 10000 + l *1000 + k * 100 + j * 10 + i; if(is_prime(t)) palind[cnt++] = t; } } int main() { freopen("pprime.in", "r", stdin); freopen("pprime.out", "w", stdout); creat_prime(); creat_palind(); int a, b; //printf("%d\n", prime[0]); //printf("%d\n", palind[0]); while(scanf("%d%d", &a, &b) == 2) { for(int i = 0; i < cnt; i++) { //printf("yes\n"); if(palind[i] >= a && palind[i] <= b) printf("%d\n", palind[i]); if(palind[i] > b) break; } } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1950310.html

最新回复(0)