题目给出一个下限，一个上限，要求求出之间的所有既是回数又是素数的数。
下边是原文描述：
Prime Palindromes
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that
finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
PROGRAM NAME: pprime
INPUT FORMAT
| Line 1: | Two integers, a and b |
SAMPLE INPUT (file pprime.in)
5 500
OUTPUT FORMAT
The list of palindromic primes in numerical order, one per line.
SAMPLE OUTPUT (file pprime.out)
5
7
11
101
131
151
181
191
313
353
373
383
解题的要点在于：
首先构造回数，然后判断是不是素数。如果你从下限遍历到上限，然后判断是不是回数和素数的话，你会死的很惨。
构造回数也是有技巧的。
在这里有两种方法：
1：
- - - - - - Aw-1 Aw-2.......Ai......A0
↑ ↑ | |
| |_______________________________↓ |
|___________________________________↓
另一种方法：
Aw-1 Aw-2.......Ai......A0 - - - - - -
↓ ↓ ↑ ↑
| |________________________________| |
|____________________________________|
如果有这样一个数：
101，的话，第一种方法是无法构造出来的。
所以采用第二种方法。
第二个关键点在于判断素数。
判断素数要从2开始，直到一个上限，但上限也是有窍门的，究竟遍历到什么地方才算节省时间呢？
注意到，如果a*b=n;
那么a<根n<b;或者相反，
因此，只需要遍历到sqrt（n）即可。
第三个要点在于构造回数的起点，如果给出的起点很高的话，从1遍历是很不合算的。
在测试用例中就分为这几种情况
low high
非常小 非常小
非常小 非常大
非常大 非常大
这是我的解法：
/*
ID: yunleis2
PROG: pprime
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cmath>
#include<string.h>
#include<vector>
using namespace std;
int longest_size=0;
bool isprime(int n);
void getNum1(int a,char * tmp,int *r1,int *r2);
void quicksort(int * a,int p,int r);
int main()
{
fstream fin("pprime.in",ios::in);
int low,high;
fin>>low>>high;
vector<int> v;
int t=high;
int lowsize=0;
while(t!=0)
{
longest_size++;
t/=10;
}
t=low;
while(t!=0)
{
lowsize++;
t/=10;
}
char * tmp=new char[longest_size*2];
/************************************************************************/
/* search from num that has (lowsize+1)/2 only search nums not divided by 2 */
/************************************************************************/
int from=pow((double)10,(lowsize+1)/2-1);
if(from%2==0)
from++;
int to=pow((double)10,(longest_size+1)/2);
while(from<=to)
{
int r1=0;
int r2=0;
getNum1(from,tmp,&r1,&r2);
/* if(r1<=high&&r1>=low)
cout<<r1;
cout<<"\t";
if(r2<=high&&r2>=low)
cout<<r2;
cout<<endl;
*/
from++;
/************************************************************************/
/* next step is to find where the num is prime */
/************************************************************************/
if(r1<=high&&r1>=low&&isprime(r1))
v.push_back(r1);
if(r2<=high&&r2>=low&&isprime(r2))
v.push_back(r2);
}
int * result=new int[v.size()];
for(int i=0;i<v.size();i++)
{
// cout<<v.at(i)<<endl;
result[i]=v.at(i);
}
delete []tmp;
quicksort(result,0,v.size()-1);
fstream fout("pprime.out",ios::out);
for(int i=0;i<v.size();i++)
{
fout<<result[i]<<endl;
}
// system("pause");
}
void getNum1(int a,char * tmp,int *r1,int *r2)
{
memset(tmp,0,longest_size);
int a1=a;
for(int i=0;a1!=0;i++)
{
tmp[i]='0'+a1%10;
a1/=10;
}
int size=strlen(tmp);
*r1=a*pow((double)10,size-1);
*r2=*r1*10;
for(int i=1;i<size;i++)
{
int tr=((int)pow((double)10,(size-1)-i))*(tmp[i]-'0');
*r1+=tr;
*r2+=tr;
}
*r2+=(tmp[0]-'0')*pow(10.0,size-1);
}
bool isprime(int n)
{
int i;
for(i=2;i<=sqrt((double)n);i++)
if(n%i==0) return false;
if(i>sqrt((double)n)) return true;
}
void swap(int * x,int * y)
{
int t=*x;
*x=*y;
*y=t;
}
int partition(int* a,int p,int r)
{
int i=p-1;
int x=a[r];
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i++;
swap(a+j,a+i);
}
}
swap(a+i+1,a+r);return i+1;
}
void quicksort(int * a,int p,int r)
{
if(p<r)
{
int q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
这是测试结果：
USER: Ma yunlei [yunleis2] TASK: pprime LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 3032 KB] Test 2: TEST OK [0.000 secs, 3032 KB] Test 3: TEST OK [0.000 secs, 3032 KB] Test 4: TEST OK [0.000 secs, 3032 KB] Test 5: TEST OK [0.000 secs, 3032 KB] Test 6: TEST OK [0.000 secs, 3032 KB] Test 7: TEST OK [0.081 secs, 3032 KB] Test 8: TEST OK [0.054 secs, 3032 KB] Test 9: TEST OK [0.081 secs, 3032 KB] All tests OK.
Your program ('pprime') produced all correct answers! This is your
submission #4 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!
这是uaco的解法：
The main problem here is that we need some way to generate palindromes. Since there are only about 10,000 palindromes less than 100,000,000, we can just test each one to see if it is prime and in the range.
To generate a palindrome, we start with the first half and reverse it. The trick is that we can repeat the middle character or not repeat the middle character. I call a palindrome with a repeated middle character "even" (because it is of even length) and one without "odd". So from the string "123", we can generate the even palindrome "123321" or the odd palindrome "12321".
We can generate all palindromes by doing the following:
- length 1: generate odd palindromes using 1..9
- length 2: generate even palindromes using 1..9
- length 3: generate odd palindromes using 10..99
- length 4: generate even palindromes using 10..99
- ...
The "generate" function does exactly this, using "genoddeven" to first generate the odd palindromes for a range and then the even ones.
The "gen" function generates an even or odd palindrome for a number by converting it to a string, making a palindrome, and converting the resulting string back to a number. Then it tests to see if the number is in the range and prime. If so, it is printed.
We could speed this up in a number of ways: use a faster primality test, don't generate palindromes past "b", etc. But this is already plenty fast, and doing such things makes the program more complex and might introduce bugs.
#include <stdio.h> #include <string.h> #include <assert.h> #include <stdlib.h> FILE *fout; long a, b;
int isprime(long n)
{
long i;
if(n == 2) return 1;
if(n%2 == 0)
return 0;
for(i=3; i*i <= n; i+=2)
if(n%i == 0)
return 0;
return 1;
}
void
gen(int i, int isodd)
{
char buf[30];
char *p, *q;
long n;
sprintf(buf, "%d", i);
p = buf+strlen(buf);
q = p - isodd;
while(q > buf)
*p++ = *--q;
*p = '\0';
n = atol(buf);
if(a <= n && n <= b && isprime(n))
fprintf(fout, "%ld\n", n);
}
void
genoddeven(int lo, int hi)
{
int i;
for(i=lo; i<=hi; i++)
gen(i, 1);
for(i=lo; i<=hi; i++)
gen(i, 0);
} void generate(void)
{
genoddeven(1, 9);
genoddeven(10, 99);
genoddeven(100, 999);
genoddeven(1000, 9999);
}
void
main(void)
{
FILE *fin;
fin = fopen("pprime.in", "r");
fout = fopen("pprime.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%ld %ld", &a, &b);
generate();
exit (0);
}
master_zed writes:
The problem can be simplified slightly by noticing that any even palindrome is divisible by 11. Therefore, 11 is the ONLY even prime palindrome. This eliminates the need to deal with 2 cases:
#include <stdio.h> #include <string.h> #include <assert.h> #include <stdlib.h> FILE *fout; long a, b;
int
isprime(long n)
{
long i;
if(n == 2)
return 1;
if(n%2 == 0)
return 0;
for(i=3; i*i <= n; i+=2)
if(n%i == 0)
return 0;
return 1;
}
void
gen(int i)
{
char buf[30];
char *p, *q;
long n;
sprintf(buf, "%d", i);
p = buf+strlen(buf);
q = p - 1;
while(q > buf)
*p++ = *--q;
*p = '\0';
n = atol(buf);
if(a <= n && n <= b && isprime(n))
fprintf(fout, "%ld\n", n);
}
void
generate(void)
{
int i;
for (i = 1; i <= 9; i++)
gen(i);
if(a <= 11 && 11 <= b)
fprintf(fout, "11\n");
for (i = 10; i <= 9999; i++)
gen(i);
}
void
main(void)
{
FILE *fin;
fin = fopen("pprime.in", "r");
fout = fopen("pprime.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%ld %ld", &a, &b);
generate();
exit (0); }
Coach Rob writes:
I guess I have a slightly different coding style than the previous two solutions. This is the same idea but coded a bit more tightly (thanks to Michael Coblenz for its kernel):
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
int primelist[100000];
int nprimes;
int isPrime(int num);
int reverse2(int i, int j);
int compare(const void *p, const void *q) { return *(int *)p-*(int *)q; }
void main (void) {
ifstream infile("pprime.in");
ofstream outfile("pprime.out");
int i, j, begin, end, num;
infile>>begin>>end;
if (begin <= 11 && 11 <=end)
primelist[nprimes++] = 11;
for (j = 0; j <= 999; j++)
for (i = 0; i <= 9; i++) {
num = reverse2(j,i);
if (num >= begin && num <=end && isPrime(num))
primelist[nprimes++] = num;
}
qsort(primelist, nprimes, sizeof(int), compare);
for (i = 0; i < nprimes; i++)
outfile << primelist[i] << "\n";
}
int
reverse2(int num, int middle) {
int i, save=num, digit, combino = 1;
for (i = 0; num; num /= 10) {
digit = num % 10;
i = 10 * i + digit;
combino *= 10;
}
return i+10*combino*save+combino*middle;
}
int isPrime(int num) {
int i;
if (num <= 3) return 1;
if (num%2 == 0 || num%3 ==0) return 0;
for (i = 5; i*i <= num; i++)
if (num %i ==0)
return 0;
return 1;
}
And here is another tightly coded solution from Anton Titov:
I guess you may find intresting my solution to Prime Palindromes as I use a function to generate palindromes, that is purely arythmetical it does not use strings, sprintf, reversion or other things. It uses recursion, but my guess is that it will outpreform all other functions listed.
Function void genPalind(int num, int add, int mulleft, int mulright)
expects 4 parameters, first is the number (N) of digits you want for your palindromes, second should be 0 for direct calls, third should be 10^(N-1) for direct calls and last one should be 1 for direct calls.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
FILE *f; int a, b; int isPrime(int num);
void genPalind(int num, int add, int mulleft, int mulright);
void tryPalind(int num);
int main(){
int i;
char first;
f=fopen("pprime.in", "r");
fscanf(f, "%d%d", &a, &b);
fclose(f);
f=fopen("pprime.out", "w");
if (a<=5)
fprintf(f, "%i\n", 5);
if (a<=7 && b>=7)
fprintf(f, "%i\n", 7);
if (a<=11 && b>=11)
fprintf(f, "%i\n", 11);
genPalind(3, 0, 100, 1);
genPalind(5, 0, 10000, 1);
genPalind(7, 0, 1000000, 1);
fclose(f);
}
void tryPalind(int num){
if (!(num&1))
return;
if (num<a || num>b)
return;
if (!(num%3) || !(num%5) || !(num%7))
return; if (!isPrime(num))
return;
fprintf(f, "%d\n", num);
}
void genPalind(int num, int add, int mulleft, int mulright){
int i, nmulleft, nmulright;
if (num==2){
for (i=0; i<10; i++)
tryPalind(add+mulleft*i+mulright*i);
}
else if (num==1){
for (i=0; i<10; i++)
tryPalind(add+mulright*i);
}
else {
nmulleft=mulleft/10;
nmulright=mulright*10;
num-=2;
for (i=0; i<10; i++)
genPalind(num, add+i*mulleft+i*mulright, nmulleft, nmulright);
}
}
int isPrime(int num){
int koren, i;
koren=(int)sqrt(1.0*num);
for (i=11; i<=koren; i+=2)
if (!(num%i))
return 0;
return 1;
}