usaco-pprime-pass

这个按自己的思路，超时，网上找到的资料，这个最简单，可是有2句很精妙：

　　  k=i;j=1;
        while(k>9){k/=10;j*=10;}
        if(k%2==0){i+=j;continue;}

跳过首位为0，2，4，6，8的回文数。能剪断一半，提升一倍的效率。

/*
ID: qq104801
LANG: C++
TASK: pprime
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>

char x[11];
int a,b;

int isprime(int n)
{    
    if (n%2==0)return 0;
    for(int i=3;i*i<=n;i+=2)
        if(n%i==0)return 0;    
    return 1;
}

int modify(int x)
{
    int t=x;x/=10;
    while(x>0){
        t=t*10+x%10;
        x/=10;
    }
    return t;
}

void test()
{    
    FILE *fin = fopen("pprime.in", "r");
    FILE *fout = fopen("pprime.out", "w"); 
    fscanf(fin,"%d %d",&a,&b);
    if(a<=5&&5<=b)fprintf(fout,"5
");
    if(a<=7&&7<=b)fprintf(fout,"7
");
    if(a<=11&&11<=b)fprintf(fout,"11
");
    int i=10,j,k;
    while(modify(i)<a)i++;
    while(modify(i)<=b)
    {
        k=i;j=1;
        while(k>9){k/=10;j*=10;}
        if(k%2==0){i+=j;continue;}
        j=modify(i);
        if(isprime(j))
            fprintf(fout,"%d
",j);
        i++;
    }   
    
    fclose(fin);
    fclose(fout);
}

main () {    
    //printf("%d
",ispalindromes(11));
    test();    
    //printf("%d
",modify(32));
    exit (0);
}

测试结果：

USER: cn tom [qq104801]
TASK: pprime
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.005 secs, 3496 KB]
   Test 2: TEST OK [0.003 secs, 3496 KB]
   Test 3: TEST OK [0.008 secs, 3496 KB]
   Test 4: TEST OK [0.011 secs, 3496 KB]
   Test 5: TEST OK [0.011 secs, 3496 KB]
   Test 6: TEST OK [0.008 secs, 3496 KB]
   Test 7: TEST OK [0.024 secs, 3496 KB]
   Test 8: TEST OK [0.022 secs, 3496 KB]
   Test 9: TEST OK [0.030 secs, 3496 KB]

All tests OK.

Your program ('pprime') produced all correct answers! This is your submission #3 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 ----
5 500
------- test 2 ----
750 14000
------- test 3 ----
123456 1123456
------- test 4 ----
97000 1299000
------- test 5 ----
9878210 9978210
------- test 6 ----
9902099 9902100
------- test 7 ----
7 10000000
------- test 8 ----
1333331 9743479
------- test 9 ----
5 100000000

Keep up the good work!
Thanks for your submission!