博客园速度非常不稳定，可能要考虑换地方了。虽然我非常喜欢博客园的模板和气氛。
这个题早就知道是怎么做的了。先求出回文数在再判断是不是素数。关键是不知道区间，那就把所有的全部求出来。虽然可能会超时，但是如果使用点技巧的话还是没问题的。
如果先筛素数的话开一亿的数组90m，肯定超内存了。据说可以只开一千万的，因为偶数就不用判了嘛。这个具体怎么实现尚不知晓。usaco的判题机构貌似极其严格，就连伪素数测试都能挑出错来。就直接拿模板上的素性测试过了。自己写的暴力测素数函数超了。代码贴一下。日后再整理吧。这两天都没怎么写解题报告了。
/*
ID: like_091
PROG: pprime
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<string>
#include<cmath>
using namespace std;
const int MAX = 15000;
int p[MAX], k = 0;
bool is_prime(int u)
{
if (u == 0 || u == 1) return false;
if (u == 2) return true;
if (u % 2 == 0) return false;
for (int i = 3; i <= sqrt(u); i += 2)
if (u % i ==0) return false;
return true;
}
void add()
{
int d[4] = {1, 3, 7, 9};
p[k++] = 5;
p[k++] = 7;
p[k++] = 11;
for (short i = 0; i < 4; i++)
for (short j = 0; j < 10; j++)
p[k++] = d[i] * 101 + j * 10;
for (short i = 0; i < 4; i++)
for (short j = 0; j < 10; j++)
p[k++] = d[i] * 1001 + j * 110;
for (short i = 0; i < 4; i++)
for (short j = 0; j < 10; j++)
for (short l = 0; l < 10; l++)
p[k++] = d[i] * 10001 + j * 1010 + l * 100;
for (short i = 0; i < 4; i++)
for (short j = 0; j < 10; j++)
for (short l = 0; l < 10; l++)
p[k++] = d[i] * 100001 + j * 10010 + l * 1100;
for (short i = 0; i < 4; i++)
for (short j = 0; j < 10; j++)
for (short l = 0; l < 10; l++)
for (short m = 0; m < 10; m++)
p[k++] = d[i] * 1000001 + j * 100010 + l * 10100 + m * 1000;
for (short i = 0; i < 4; i++)
for (short j = 0; j < 10; j++)
for (short l = 0; l < 10; l++)
for (short m = 0; m < 9; m++)
p[k++] = d[i] * 10000001 + j * 1000010 + l * 100100 + 11000;
}
int main()
{
ifstream cin("pprime.in");
ofstream cout("pprime.out");
add();
int a, b;
cin>>a>>b;
int q = 0;
while (p[q] < a)++q;
while (q < k)
{
if (p[q] <= b && is_prime(p[q]))
cout<<p[q]<<endl;
q++;
}
return 0;
}
原文链接: https://www.cnblogs.com/neulike/archive/2011/02/24/1964227.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/21501
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
