Skip to analysis
This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!
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
HINTS (use them carefully!)
Hint 1
Generate the palindromes and see if they are prime.
Hint 2
Generate the palindromes and see if they are prime.
Generate palindromes by combining digits properly. You might need more than one of the loops like below.
/* generate five digit palindrome: */
for (d1 = 1; d1 <= 9; d1+=2) { /* only odd; evens aren't so prime */
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;
//... deal with palindrome ...
}
}
}
CODE
Java
C++
Pascal
ANALYSIS
Russ Cox
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
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 & Michael Coblenz
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;
}
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;
}
Back to top