题解 - Vijos

4

zhangboju LV 7 @ 2019-08-01 09:17:33

打表
时间快到飞起（最慢13ms）
#include <bits/stdc++.h>
using namespace std;
int a[]={0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
bool b[10000000];
int main()
{
int m,n;
cin>>m>>n;
memset(b,false,sizeof(b));
for(int i=1;i<=10000000;i++)
{
b[a[i]]=true;
if(a[i]==0)
{
break;
}
}
for(int i=m;i<=n;i++)
{
if(b[i]==true)
{
printf("%d\n",i);
}
if(i>9989899)
{
break;
}
}
}

1

__cby__ LV 7 @ 2022-04-29 20:32:02

答案如下:全场最好理解没用任何奇怪的函数(sqrt除外)

#include <iostream>
#include <cmath>
using namespace std;
bool SUSHU(int a){//判断素数
    if(a==1){//虽然题目中最小是5 ,但我初始化时v(1个列表)全设为1
        return false;//返回
    }
    if(a%6!=1&&a%6!=5){//自己想想看,为什么,
        return false;
    }
    int i=a;
    while (i>0){
        i/=10;
    }
    if(i==2||i==4||i==5||i==6||i==8){//个位(i) 不能是24568
        return false;
    }
    int tmp = sqrt(a);//开方更节省时间
    for(i = 5; i <= tmp; i+=6) {
        if(a % i == 0 || a%(i+2)==0) return false;
    }
    return true;
}
bool hui(int a){//判断回文串
    if(a==1){//与上面同理
        return false;
    }
    int j=0,i=a;
    for (i=a;i>0;i/=10){
        j=j*10+i%10;//正过来=反过来
    }
    return a==j; 
}
int main(int argc, char** argv) {
    int i,j,q=0;
    int v[500000] = {0};
    for(int idx=0; idx<500000; idx++){
        v[idx] = 1;//初始化为1
    }
    
   cin>>i>>j;
  if(i>10000000){//1千万~1亿之间无符合题目的数
    i=10000000;
    }
    if(j>10000000){//1千万~1亿之间无符合题目的数
        j=10000000;
    }
    for (int n=i;n<=j;n++){
        if(hui(n)){
       v[q]=n;q++;//筛选回文数;几个回文数
        }
    }
    for (int n=0;n<=q;n++){//
        if(SUSHU(v[n])){//如果是素数
        cout<<v[n]<<endl;//打印
        }
    }
    return 0;
}

1

liushaoyu2333 LV 8 @ 2019-07-25 15:52:43

1、求回文数：首先判断数字i有多少位(a)，然后比较最高位（i/10^a）和最低位(i%10)是否相等，相等的话就把最高位和最低位去掉
2、因为m最小为5，所以大可不必去搜索偶数，也就是说for(i=m;i<n;i+=2)就可以缩小一半范围！（但是你要先判断m是不是偶数，是的话就先+1）
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool sushu(int i)
{
int j;bool s=true;
if(i%2==0) s=false;
for(j=3;j<=sqrt(i);j+=2) if(i%j==0) {s=false;break;}
return s;
}
bool huiwen(int i)
{
bool hw=true;int j,k=1,l,a,x=i,y;
while(x/10!=0) {x=x/10;k++;}
y=k;
x=i;
for(j=1;j<=k/2;j++)
{
a=1;
for(l=1;l<y;l++) a=a*10;
if(x%10==x/a) {x-=x/a*a;x=x/10;y-=2;} else {hw=false;break;}
}
return hw;
}
int main()
{
int m,n,i=0;
cin>>m>>n;
if(m%2==0) m++;
for(i=m;i<=n;i+=2) if(huiwen(i)) if(sushu(i)) cout<<i<<endl;
return 0;
}

1

ToSoul LV 5 @ 2017-09-22 17:19:00

虽然代码写得很丑( • ̀ω•́ )✧ 但在输出时略加操作居然过了ヾ(ｏ･ω･)ﾉ真是道难题呢！

(:з」∠)唔

算法：

枚举生成数每一位（数组存）的**DFS**，加上**剪枝**。

重点：

1.既然我们所求的是回文数，那我们为什么直接求它的一半呢？
（规避了回文数判断的问题，大力缩小搜索范围。）
当我们想要得到我们的回文数字时，只需要按 "复制这一半" 和 "复制一半并中间数字重叠" 两种方式即可去判断素数了。

2.不存在 "2....2" "4....4” "4....4" "5....5" "6....6" "8....8" 这一类的数字。
（因此我们可以在搜索的最初展开时减掉大量不必的情况。）
因为那上面形式的数很明显不是素数啦。

3.一定要当数字的长度在N与M之间时再判断是否合法。
（因为合成数字的操作很费时间！）
( 。ω。) 其实是程序写的辣鸡啦。

可优化之处：

比如判素数来个miller-rabin。
DFS写得机灵点。
不如直接打个表吧。（素数表，答案表...）

最后劝一句，请各位不要忽视搜索的技巧。

#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF (0x3f3f3f3f)
#define LINF (0x3f3f3f3f3f3f3f3fLL)
using namespace std;
int L,R;
vector<int> Num,Ans;
bool CHECK1 (int num) 
{
    vector<int> numb;
    while(num>0) {
        numb.push_back(num%10); 
        num/=10;
    }
    int len=numb.size();
    if (len%2) 
    {
        for(int i=0;i<len/2;i++)    
            if(numb[i]!=numb[len-i-1]) return 0;
    }
    else 
    {
        for(int i=0;i<len/2;i++)    
            if(numb[i]!=numb[len-i-1]) return 0;    
    }
    return 1;
}
bool CHECK2 (int num) 
{
    int sqr=sqrt(num);
    for(int i=2;i<=sqr;i++) 
        if(num%i==0) return 0;
    return 1;    
}
int COUNT1 () 
{
    int num=0,len=Num.size();
    while(len>0) 
    {
        num=num*10+Num[Num.size()-len];
        len--;
    }
    len=Num.size()-1;
    while(len>=0) 
    {
        num=num*10+Num[len];
        len--;
    }
    return num;
}
int COUNT2 () 
{
    int num=0,len=Num.size();
    while(len>0) 
    {
        num=num*10+Num[Num.size()-len];
        len--;
    }
    len=Num.size()-2;
    while(len>=0) 
    {
        num=num*10+Num[len];
        len--;
    }
    return num;
}
void DFS(int len,int lenl,int lenr) 
{   
    if(len*2>=lenl&&len*2-1<=lenr) {
        int num1=COUNT1(),num2=COUNT2();
        if(num1<=R&&num1>=L) 
            if(CHECK1(num1)) 
                if(CHECK2(num1)) Ans.push_back(num1);
        if(num2<=R&&num2>=L) 
            if(CHECK1(num2)) 
                if(CHECK2(num2)) Ans.push_back(num2);
        if(num1>R&&num2>R) return;
    }
    if (len*2-1>lenr) return;
    for(int i=0;i<=9;i++) {
        if(len==0) 
            if (i==0||i==2||i==4||i==6||i==8||i==5) continue;
        Num.push_back(i);
        DFS(len+1,lenl,lenr);
        Num.pop_back(); 
    }
} 
int main ()
{
    cin>>L>>R;
    DFS(0,(int)(log(L)/log(10))+1,(int)(log(R)/log(10))+1);
    if(L<=5) Ans.push_back(5);
    sort(Ans.begin(),Ans.end());
    for(int i=0;i<Ans.size();i++) 
        if (Ans[i]>=5) cout<<Ans[i]<<endl; 
    return 0;
}

0

猫粮寸断 LV 10 @ 2018-04-11 19:33:52

没什么需要特别注意的，直接dfs就可以，感觉此题是素数肋骨的加强版
5和7输不出来需要特判一下
但是下面给的代码会MLE最后一个点，因为我用的是欧拉筛判素，然后就被完美的卡掉了，改成朴素的根号n判素就可过（但是我懒）

#include<iostream>
#include<algorithm>
using namespace std;
int c[6],ans[20010],s[100000010];
int n,m,now,len;
void dfs(int w)
{
    if(2*w>=len)
     return ;
    int i,sum1=0,sum2=0,lin=1,lin1,j,sum;
    if(c[w]&1)
    {
    for(i=w;i>=1;i--)
     {
        sum1+=lin*c[i];
        lin*=10;
     }
     lin1=lin;
    for(i=1;i<=w;i++)
     {
        sum2+=lin*c[i];
        lin*=10;
     }
    if(sum1+sum2>=n&&sum1+sum2<=m) 
     if(!s[sum1+sum2])
     { 
        now++;
        ans[now]=sum1+sum2;
     }

     for(i=0;i<=9;i++)
      {
        sum=0;
        sum=sum1+lin1*i+sum2*10;
        if(sum>=n&&sum<=m)
         if(!s[sum])
          {
            now++;
            ans[now]=sum;
          }
      }
     
    }
    for(i=0;i<=9;i++)
    {
        c[w+1]=i;
        dfs(w+1);
        c[w+1]=0;
    }
}
int main()
{
    int i,j,ha=1;
    cin>>n>>m;
    for(i=1;;i++)
    {
        ha*=10;
        if(ha>=m)
         break;
    }
    len=i;
    s[1]=1;
    for(i=2;i<=m;i++)
     {
      if(!s[i])
       for(j=2;j*i<=m;j++)
        s[i*j]=1;
     }
     if(5>=n&&5<=m)
     cout<<5<<endl;
    if(7>=n&&7<=m)
     cout<<7<<endl;
    dfs(0);
    sort(ans+1,ans+now+1);
    for(i=1;i<=now;i++)
     cout<<ans[i]<<endl;
    return 0;
}

0

!TNT! LV 8 @ 2017-07-03 18:55:35

真几把骚，楼下的m=min(m,10000000)厉害了
直接上素数筛

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,w[20000000],t;
bool vis[100000010]={0};
void prime(){
    for(int i=2;i<=m;++i){
        if(!vis[i]) w[t++]=i;
        for(int j=0;j<t&&i*w[j]<=m;++j){
            vis[i*w[j]]=1;
            if(i%w[j]==0) break;
        }
    }
}
inline bool ok(int x){
    int s[10],l=0;
    for(;x;x/=10) s[l++]=x%10;
    for(int i=0;i<(l>>1);++i) if(s[i]!=s[l-i-1]) return 0;
    return 1;
}
int main(){
    scanf("%d%d",&n,&m); prime();
    int i=lower_bound(w,w+t,n)-w;
    while(w[i]<n) i++;
    for(;i<t;++i) if(ok(w[i])) printf("%d\n",w[i]);
}

ShuraK.彧 @ 2017-11-21 16:54:20

###卧槽，你这数组能tm开下？

0

飞天小象 LV 4 @ 2017-06-13 19:47:08

import java.util.Scanner;

public class Test {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String in = input.nextLine();
String[] nums = in.split(" ");
int M = Integer.parseInt(nums[0]);
int N = Integer.parseInt(nums[1]);
for(int i = M;i <= N;i++){
if(isPrime(i) && isAntitone(i)){
System.out.println(i);
}
}
}

private static boolean isAntitone(int i) {
boolean flag = true;
String temp = i+"";
char[] cs = temp.toCharArray();
int length = cs.length;
for(int j = 0;j < length/2;j++){
if(cs[j] != cs[length-1-j]){
flag = false;
break;
}
}
return flag;
}

private static boolean isPrime(int i) {
boolean flag = true;
for (int j = 2; j < i; j++) {
if (0 == i % j) {
flag = false;
break;
}
}
return flag;
}
}

0

我是神 LV 10 @ 2016-11-28 15:07:11

#include<stdio.h>

#include<string.h>

int prime[4000];

int psize;

int from, to;

void getPrime(){

memset(prime, 0, sizeof(prime));

psize = 0;

int i,j;

bool a[10000];

memset(a, -1, sizeof(a));

for (i = 2; i < 10000; i++){

if (!a[i])continue;

prime[psize++] = i;

for (j = i + i; j < 10000; j+=i)a[j] = false;

}

}

bool isPrime(int n){

int i;

for (i = 0;prime[i]*prime[i]<=n; i++)if (n%prime[i] == 0)return false;

return true;

}

void one(){

if (from>7)return;

if (from == 5)printf("5\n");

printf("7\n");

}

void three(){

if (from > 999)return;

int i, j,k;

int a[4] = { 1, 3, 7, 9 };

for (i = 0; i < 4;i++)

for (j = 0; j < 10; j++){

k = a[i] * 100 + j * 10 + a[i];

if ( k< from)continue;

if (k>to)return;

if (isPrime(k))printf("%d%d%d\n", a[i], j,a[ i]);

}

}

void five(){

if (from>99999)return;

int a[4] = { 1, 3, 7, 9 };

int i, j, k, l;

for (i = 0; i < 4;i++)

for (j = 0; j < 10;j++)

for (k = 0; k < 10; k++){

l = a[i] * 10000 + j * 1000 + k * 100 + j * 10 + a[i];

if (l<from)continue;
if (l>to)return;

if (isPrime(l))printf("%d%d%d%d%d\n", a[i], j, k, j, a[i] );

}

}

void seven(){

if (from>9999999)return;

int a[4] = { 1, 3, 7, 9 };

int i, j, k, l,m;

for (i = 0; i < 4; i++)

for (j = 0; j < 10; j++)

for (k = 0; k < 10; k++)

for(m=0;m<10;m++){
l = a[i] * 1000000 + j * 100000 + k * 10000 + m * 1000 +k*100+j*10+ a[i];
if (l<from)continue;
if (l>to)return;

if (isPrime(l))printf("%d%d%d%d%d%d%d\n", a[i], j, k,m,k, j, a[i]);

}

}

int main(){

getPrime();

prime[psize++]=10001;

scanf("%d%d", &from, &to);

one();

if (11 >= from && 11 <= to)printf("11\n");

three(); five(); seven();

return 0;

}

0

我是百度啦啦啦 LV 8 @ 2016-11-16 11:04:25

#include<bits/stdc++.h>
using namespace std;
bool check(int i)
{
    for(int j=2;j*j<=i;j++) {
        if(i%j==0) return 0;
    }
    return 1;
}
bool huiwen(int i)
{
    int k=i,l=0;
    int a[11];
    for(int j=0;k>0;k/=10,j++) l++,a[j]=k%10;
    for(int j=0,k=l-1;j<(l+1)/2;j++,k--) {
        if(a[j]!=a[k]) return 0;
    }
    return 1;
}
int main()
{
    int i,j,k,l,n,m;
    cin>>n>>m;
    m = min(m,10000000);
    for(i=n;i<=m;i++) {
        if(i>3&&i%10!=2){
            if(huiwen(i)) {
                if(check(i)) cout<<i<<endl;
            }
        }
        
    }
    return 0;
}

wzq1w @ 2019-01-30 13:57:35

m = min(m,10000000);太强了！

0

1263659722 LV 10 @ 2016-11-04 09:25:52

真的是醉了。。。

#include<bits/stdc++.h>
#define pi acos(-1.0)
#define ll long long
#define N 11
#define INF 0x7fffffff
using namespace std;
int a[N];

bool check(int x)
{
int len=0,b=x,c=x;
while(b)
{
b/=10;
len++;
}
if(!len%2)
return false;
if(!x%2)
return false;
memset(a,0,sizeof(a));
for(int i=1;i<=len;i++)
{
a[i]=x%10;
x/=10;
}
for(int i=1;i<=(len+1)/2;i++)
{
if(a[i]!=a[len+1-i])
return false;
}
for(int i=2;i<=sqrt(c);i++)
if(c%i==0)
return false;
return true;
}
int main()
{
int L,R;
scanf("%d%d",&L,&R);
R=min(R,10000000);
for(int i=L;i<=R;i++)
{
if(check(i))
printf("%d\n",i);

}
return 0;
}

0

chronix LV 8 @ 2016-08-20 22:35:37

#include <cstdio>

int A[]={1,2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};

int main(){
int l,r,flag=0;
scanf("%d%d",&l,&r);
for(int i=0;i<782;i++){
int t=A[i];
if(A[i]>=l&&A[i]<=r)

flag=1;
if(A[i]>r)
break;
if(flag==1)
printf("%d\n",A[i]);
}
return 0;
}

0

hzk123 LV 9 @ 2016-08-19 20:45:52

#include <iostream>
#include <cstdio>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#define ll long long
using namespace std;
const int S=50;//随机算法判定次数，S越大，判错概率越小

//计算 (a*b)%c. a,b都是long long的数，直接相乘可能溢出的
// a,b,c <2^63
long long mult_mod(long long a,long long b,long long c)
{
a%=c;
b%=c;
long long ret=0;
while(b)
{
if(b&1){ret+=a;ret%=c;}
a<<=1;
if(a>=c)a%=c;
b>>=1;
}
return ret;
}

//计算 x^n %c
long long pow_mod(long long x,long long n,long long mod)//x^n%c
{
if(n==1)return x%mod;
x%=mod;
long long tmp=x;
long long ret=1;
while(n)
{
if(n&1) ret=mult_mod(ret,tmp,mod);
tmp=mult_mod(tmp,tmp,mod);
n>>=1;
}
return ret;
}

//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(long long a,long long n,long long x,long long t)
{
long long ret=pow_mod(a,x,n);
long long last=ret;
for(int i=1;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret==1&&last!=1&&last!=n-1) return true;//合数
last=ret;
}
if(ret!=1) return true;
return false;
}

// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;

bool Miller_Rabin(long long n)
{
if(n<2)return false;
if(n==2)return true;
if((n&1)==0) return false;//偶数
long long x=n-1;
long long t=0;
while((x&1)==0){x>>=1;t++;}
for(int i=0;i<S;i++)
{
long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
if(check(a,n,x,t))
return false;//合数
}
return true;
}

ll pw10[10];
int ans[100000];
int main()
{
int n,m;
int cnt=0;
pw10[0]=1;
for (int i=1;i<=10;i++)
pw10[i]=pw10[i-1]*10;
scanf("%d%d",&n,&m);
for (int i=1;i<=10000;i++)
{
ll temp=i;
ll sum=0;
int level=0;
while (temp>0)
{
sum=sum*10+ temp % 10;
temp/=10;
level++;
}
temp=i*pw10[level]+sum;
if (temp>=n && temp<=m && Miller_Rabin(temp))
ans[cnt++]=temp;

for (int k=0;k<=9;k++)
{
temp=i*pw10[level+1]+k*pw10[level]+sum;
if (temp>=n && temp<=m && Miller_Rabin(temp))
ans[cnt++]=temp;
}
}

if ( 5>=n && 5<=m) ans[cnt++]=5;
if ( 7>=n && 7<=m) ans[cnt++]=7;
sort(ans,ans+cnt);
for (int i=0;i<cnt;i++)
printf("%d\n",ans[i]);
return 0;
}

0

lrj124 LV 10 @ 2016-07-21 22:17:30

打什么表啊？

记录信息
评测状态    Accepted
题目  P1042 捕风捉影
递交时间    2016-07-21 22:14:19
代码语言    C++
评测机 ShadowShore
消耗时间    1888 ms
消耗内存    556 KiB
评测时间    2016-07-21 22:14:22
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #2: Accepted, time = 62 ms, mem = 552 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 556 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #6: Accepted, time = 625 ms, mem = 552 KiB, score = 10
测试数据 #7: Accepted, time = 546 ms, mem = 552 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #9: Accepted, time = 593 ms, mem = 552 KiB, score = 10
Accepted, time = 1888 ms, mem = 556 KiB, score = 100
代码
#include <bits/stdc++.h>
bool check(int x) {
  int len = 0,b = x,c = x;
  for (;b;len++) b /= 10;
  if(!len%2) return false;
  int a[101];
  if (!x%2) return false;
  memset(a,0,sizeof(a));
  for(int i = 1;i <= len;i++) {
    a[i] = x%10;
    x /= 10;
  }
  for (int i = 1;i <= (len+1)/2;i++)
    if (a[i] != a[len+1-i]) return false;
  for (int i = 2;i <= sqrt(c);i++)
    if(c%i==0) return false;
  return true;
}
int main() {
  int L,R;
  scanf("%d%d",&L,&R);
  R = std :: min(R,10000000);
  for (int i = L;i <= R;i++)
    if (check(i)) printf("%d\n",i);
  return 0;
}

0

wang_yanheng LV 10 @ 2016-07-21 16:27:22

不明白为什么这种题会有人要打表... 还有拜托打表的人也得把表弄对，居然把 0 和 1 当素数、2 当合数，实在无语。
随便写个DFS 10^10内秒杀无压力

#include <stdio.h>
#include <math.h>

int num[15]; //DFS时记录回文数数码
int a, b; //题中所给区间端点

int isPrime(int x){
int i, bound = ceil(sqrt(x));
if(x == 2)
return 1;
if(x <= 1)
return 0;
for(i=2; i<=bound; i++){
if(x%i == 0)
return 0;
}
return 1;
}
void print(const int length){
//将 num 数组还原成数，然后验证合法性
int n, i;
for(n=0, i=0; i<=(length-1)/2; i++)
n = n*10 + num[i];
for(; i<length; i++)
n = n*10 + num[length-i-1]; //补全剩下一半
if(n>=a && n<=b && isPrime(n))
printf("%d\n", n);
}
void search(const int length, int index){
//生成长度为length的回文数的前半部分，将每一位都记录到num数组。index代表枚举到第几位。
//注意枚举到长度的一半即可，剩下一半与前面一半对称
int i;
if(length <= index*2){
print(length);
return;
}
for(i=0; i<10; i++){
if(i%2==0 && index==0 && length>1)
continue;
num[index] = i;
search(length, index+1);
}
}
int main(){
int c, d; //分别代表 a 和 b 的位数
scanf("%d %d", &a, &b);
c = (int)(log(a)/log(10))+1;
d = (int)(log(b)/log(10))+1;
for(; c<=d; c++)
search(c, 0);
return 0;
}

z20c12h @ 2017-09-22 15:57:42

枚举一半的想法很厉害。

0

zhouyuyang1 LV 10 @ 2016-05-05 20:50:19

var
a:array [1..780] of longint=(0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899);
c,b,i:longint;
begin
read(c,b);
for i:=1 to 780 do
if (a[i]>=c) and (a[i]<=b) then writeln(a[i]);
end.

z20c12h @ 2017-09-22 14:16:09

23333

0

hjp_handsome LV 8 @ 2015-09-17 13:32:55

总计15ms

var m,n,s,b,x,c,v:longint;
z:array[1..4]of longint=(1,3,7,9);

function su(a:longint):boolean;
var s,d:longint;
begin
for s:=1 to (trunc(sqrt(a)) div 2) do
if a mod (s*2+1)=0 then exit(false);
exit(true);
end;

procedure main;
begin
readln(m,n);

if 5>=m then writeln(5);

for x:=1 to 4 do
if su(z[x]) then if (z[x]>=m) then
if z[x]<=n then writeln(z[x]) else exit;

if 11>=m then
if 11<=n then writeln(11) else exit;

for x:=1 to 4 do
for c:=0 to 9 do
begin
s:=z[x]*101+c*10;
if su(s) then if s>=m then
if s<=n then writeln(s) else exit;
end;

for x:=1 to 4 do
for c:=0 to 9 do
begin
s:=z[x]*1001+c*110;
if su(s) then if s>= m then
if s<=n then writeln(s) else exit;
end;

for x:=1 to 4 do
for c:=0 to 9 do
for v:=0 to 9 do
begin
s:=z[x]*10001+c*1010+v*100;
if su(s) then if s>=m then
if s<=n then writeln(s) else exit;
end;

for x:=1 to 4 do
for c:=0 to 9 do
for v:=0 to 9 do
begin
s:=z[x]*100001+c*10010+v*1100;
if su(s) then if s>=m then
if s<=n then writeln(s) else exit;
end;

for x:=1 to 4 do
for c:=0 to 9 do
for v:=0 to 9 do
for b:=0 to 9 do
begin
s:=z[x]*1000001+c*100010+v*10100+b*1000;
if su(s) then if s>=m then
if s<=n then writeln(s) else exit;
end;

for x:=1 to 4 do
for c:=0 to 9 do
for v:=0 to 9 do
for b:=0 to 9 do
begin
s:=z[x]*10000001+c*1000010+v*100100+b*11000;
if su(s) then if s>=m then
if s<=n then writeln(s) else exit;
end;
end;

begin
main;
end.

0

limuye LV 9 @ 2015-08-10 14:25:43

#include<cstdio>
using namespace std;
main()
{
int a[780]={0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899},m,n,i; scanf("%d%d",&m,&n); for(i=1;i<=779;i++) { if(a[i]>=m&&a[i]<=n) printf("%d\n",a[i]); if(a[i]>n) return 0; } }

0

haoziyu LV 9 @ 2015-08-01 10:43:44

#include<cstdio>
#include<iostream>
using namespace std;
int a[780]={0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
int main()
{
int m,n,i;
scanf("%d%d",&m,&n);
for(i=1;i<=779;i++)
{
if(a[i]>=m&&a[i]<=n)printf("%d\n",a[i]);
if(a[i]>n) return 0;
}
return 0;
}

0

TenderRun LV 10 @ 2015-07-24 18:51:03

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 276 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 280 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 280 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #6: Accepted, time = 889 ms, mem = 280 KiB, score = 10
测试数据 #7: Accepted, time = 717 ms, mem = 276 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #9: Accepted, time = 873 ms, mem = 280 KiB, score = 10
Accepted, time = 2602 ms, mem = 280 KiB, score = 100

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
int how;
bool is_it(int a)
{
int total=0;
int b=a;
int c=a;
for(total=0;b!=0;total++)b/=10;
if(total%2==0)
return false;
how=total;
int h[100];
int jf=a%10;
if(jf==0||jf==2||jf==4||jf==5||jf==6||jf==8)
return false;
memset(h,0,sizeof(h));
for(int i=1;i<=how;i++)
{
h[i]=a%10;
a/=10;
}
for(int i=1;i<=(how+1)/2;i++)
{
if(h[i]!=h[how+1-i])
return false;
}total=1;
for(int i=2;i<=sqrt(c);i++)
if(c%i==0)
{ total=0;
break;
}
if(total==0)
return false;

return true;

}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
int h=min(b,9989900);
for(int i=a;i<=h;i++)
{
if(is_it(i)||i==11||i==5)
printf("%d\n",i);
}
}

0

q234rty LV 10 @ 2015-05-06 18:20:53

注意到一个n位的数对应两个回文数:一个有2n位，另一个有2n-1位。（比如2341对应14322341和1432321，但末位为0的数如1230，无法构成回文数）所以枚举1-9999内的所有末位不为0的数，判断每个数对应的两个回文数是不是素数即可。
（考虑到9850589这样的回文数的存在，枚举每个数时，要不停的向前添加0，直到达到4位为止）
（另外，得到的结果不一定是排好序的，所以要排序）
UPD:实际上这个解法是可以优化的，首先注意到2n位的回文数一定能被11整除（回文数性质），还有原来是偶数的数产生的回文数也是偶数。

var
    m,n,i,x1,num,j:longint;
    a:array[1..100000] of longint;
    code:integer;
    s,s2:string;
procedure swap(x,y:longint);
var t:longint;
begin
    t:=a[x];
    a[x]:=a[y];
    a[y]:=t;
end;

procedure qsort(l,r:longint);  //排序
var
    i,j,x:longint;
begin
    i:=l;j:=r;x:=a[random(r-l+1)+l];
    repeat
        while a[i]<x do inc(i);
        while a[j]>x do dec(j);
        if i<=j then begin swap(i,j);inc(i);dec(j);end;
    until i>j;
    if i<r then qsort(i,r);
    if j>l then qsort(l,j);
end;
function isprime(x:longint):boolean;
var max,i:longint;
begin
    max:=trunc(sqrt(x));
    if x=1 then exit(true);
    for i:=2 to max do
        if x mod i=0 then exit(false);
    exit(true);
end;
begin
    readln(m,n);
    num:=0;
    if (m<=11) and (n>=11) then begin inc(num);a[1]:=11;end;  //特判
    for i:=1 to 9999 do
    begin
        if i mod 2=0 then continue;
        str(i,s);
    repeat
            s2:='';
            for j:=1 to length(s) do
                s2:=s2+s[length(s)-j+1];
            val(copy(s2,1,length(s2)-1)+s,x1,code);
            if (x1>=m) and (x1<=n) and isprime(x1) then begin num:=num+1;a[num]:=x1;end;
        s:='0'+s;  //添加0
    until length(s)>4;
    end;
    qsort(1,num);
    for i:=1 to num do
        writeln(a[i]);
end.

题解

191 条题解

捕风捉影

信息

状态

开发

支持

题解

191 条题解

捕风捉影

信息

状态

开发

支持

还没有账户？

登录