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
/*
ID: amitc1
PROG: pprime
*/

/* Generate all the palindromic sequences
for all lengths and then locate the required
number. Remember you have to generate only
for half the length of the entire sequence and
the rest of the number is constructed (odd+even length)
to meet the palindromic constraint and finally tested
for primality */
The solution :

Code:

/*

PROG: pprime
*/

/* Generate all the palindromic sequences
for all lengths and then locate the required
number. Remember you have to generate only
for half the length of the entire sequence and
the rest of the number is constructed (odd+even length)
to meet the palindromic constraint and finally tested
for primality */

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

int genpal1(int no)
{
  char buf[50];
  sprintf(buf,"%d",no);
  string oldi(buf);
  string abc;
 
  reverse(oldi.begin(),oldi.end()); 
  abc=string(buf)+oldi;
 
  sscanf(abc.c_str(),"%d",&no);
  return no;
}

int genpal2(int no)
{
  char buf[50];
  sprintf(buf,"%d",no);
  string oldi(buf);
  string abc;
  oldi.erase(oldi.end()-1);
  reverse(oldi.begin(),oldi.end()); 
  abc=string(buf)+oldi;
 
  sscanf(abc.c_str(),"%d",&no);
  return no;
}


bool isprime(int no)
{
  for (int k=2; k<=sqrt(no); k++)
    if (no%k==0) return false;
  return true;
}

void main()
{
  fstream fin,fout;
  int i,a,b;
  fin.open("pprime.in",ios::in);
  cin=fin;
  fout.open("pprime.out",ios::out); 
 
  cin >> a >> b;
  vector<int> primes;
  for (i=1; i<=10009; i++)
  {
    int k=0,l=0;
    k=genpal1(i);
    l=genpal2(i);
   
    if ((l>=a) && (l<=b))
      if (isprime(l)) primes.push_back(l);
    if ((k>=a) && (k<=b))
      if (isprime(k)) primes.push_back(k);   
  }
  sort(primes.begin(),primes.end());
  for ( i=0; i<primes.size(); i++)
    fout << primes[i] << endl;
  fout.close();   
}

I am providing an equivalent C code. Check it out :

Code:

#include<stdio.h>
#include<math.h>
long int primecheck(long int x);
main()
{
long int a=2,c,d,e=0,i,j,l,k=0,z;
long int p[80];
while (a<=500)
{
j=primecheck(a);
if (j==0)
{
c=a,i=0,d=0;
while (c!=0)
{
p[i]= (c%10);
++i;
c/=10;
}
z=(i-1);
for (l=0;l<=z/2;++l)
{
if (p[l]==p[z-l])
++d;
else
break;
}
if (d==(z+2)/2)
{
++e,++k;
if (e==1)
printf("%ld",a);
else
printf(", %ld",a);
}
}
++a;
}
printf("\n\nThe total number of palindromic primes between 2 and %ld is %ld.\n\n",a-1,k);
}
long int primecheck(long int x)
{
long int m=2;
while (m<x)
{
if ((x%m)==0)
break;
++m;
}
if (m==x)
return(0);
else
return(1);
}


By the way, I ran the C++ code posted here and the program didn't run. Gave loads of errors .

what errors ?

Dunno. I don't know C++, but I have Quincy C++ compiler where I copy-pasted the code and tried to run it, when it gave errors I cannot understand .

Here is a TURBO c++ program to find prime palindromic numbers after a certain(input) number..

Code:

#include<iostream.h>
#include<conio.h>
#include<process.h>

void main()
{
clrscr();
unsigned long a,b[10],z=10;
int i=0,j=0,k=0,m=0,c=1,g=2,f=6;
cin>>a;
if (a==1)
{
  cout<<a;
  cout<<"\nnot prime";
  getch();
  exit(0);
}
b:while(k==0)
{
  b[i]=((a+j)%z);
  if (b[i]==(a+j))
  {
    if(c==2)
    {
      goto a;
    }
    c++;
  }
  b[i]=b[i]/(z/10);
  i++;
  z=z*10;
}
a:for(m=0;m<i;m++)
  {
    if (b[m]!=b[i-m-1])
    {
      j++;
      i=0;
      c=1;
      g=1;
      z=10;
      goto b;
    }
    else if(b[m]==b[i-m-1])
    {
       g=0;
       continue;
    }
  }
if(g==0)
{
  for(int l=2;l<b[i]/2;l++)
  {
    if(b[i]%l==0)
    {
      j++;
      i=0;
      c=1;
      g=1;
      z=10;
      goto b;
    }
    else
    {
      f=1;
      continue;
    }
  }
}
c:if (f==1)
  {
    cout<<endl<<"no. is prime\n";
  }
cout<<b[i];
getch();
}

Hi, joined codemiles because I saw this post and I'm interested in palindrome and reverse primes, specifically those that are 4n+1 type primes and only those with consecutive factors. For instance 181 can be expressed as 9^2 + 10^2. To date the
largest palindrome prime of this type I have found is 3187813 = 1262^2 + 1263^2.

What I call a 'reverse' prime is one that is a 4n+1 prime resulting from the sum of 2 consecutive numbers squared, both forward and backward. 12641 <-----> 14621 is the only one I've found so far that meets these requirements. I would like any suggestions or for someone with better programming/math skills to advise/help me improve my methods.

I've used the following code to check 4n+1 type primes with consecutive factors up to 8M^2.

Code:

/* otto.c                                                       04.10.2010
*
* Program to search for what I refer to as otto and reverse prime numbers that are
* also 4n + 1 type primes as described by Fermat.  An "otto"  prime is one that is
* the same forward/backwards. Further the prime should be the sum of 2 CONSECUTIVE
* integers squared ( (n)^2 + (n + 1)^2 ). For example  181 is a 4n + 1  type prime
* that can be expressed as  9^2 + 10^2 (the sum of 2 consecutive numbers squared).
* To now the largest otto prime I know of is... 3187813.
*
* A reverse prime is one that is a  4n + 1 type prime  both forward and backwards,
* and is also the sum of consecutive integers squared forwards and backwards.  So
* far I have discovered only one prime...12641 <---> 14621 that qualifies with all
* these requiements.  Luckily this number occurs early in the list!
*
* compile with $> gcc -o otto otto.c -lm
*
*/

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

/* adjust defines as needed */
#define MAX_BUF 2500
#define MAX_RANGE 20000

int isit_prime(long long);
int magnitude(long long, int *);

int main(void)
{
    unsigned long long result = 0;
    unsigned long x = 5; unsigned long int y = 6;
    int a = 0; int b = 0;
    int cnt = 0; int itr = 0; int chk_value = 0;
    int power = 0;              /* 10 to the nth power */
    int *pwr = &power;
    char buf[MAX_BUF][30];
    int skip_val[6] = {2, 2, 1, 2, 2, 1};
   
   
    /* initializing first element to zero will cause C to
     * automatically init. the remainder of array to zero */
    buf[0][0] = 0;
    char rev[30]= {0};

    /* use answer.quot and answer.rem    */
    lldiv_t answer;
   
    /* Generate Prime List */
    while(x < MAX_RANGE)
    {
        itr = 0;
        cnt = 6;
       
        while(cnt)
        {
            result = powl(x, 2) + pow(y, 2);
     
            /*
             * 
             * Since I conjecture that the last digit of all 4n+1 type primes that result
             * from the sum of 2 consecutive numbers squared  is a 1 or 3 and, further if
             * it is a 1, the next to last number is even (0,2,4,6,8) and if it is 3 then
             * the next to last number must be 1 only. Using the last 2 digits as a gate-
             * keeper reduces the amount of values processed significantly. We only allow
             * numbers that begin with 1(2,4,6,8 or 0) or 31.
             *
             * All of the data manipulation to derive 'chk_value' is done in magnitude().
             *
             */
             
            /* 2 highest magnitude digits...'gatekeeper' */
            chk_value = magnitude(result, pwr);
   
            /* Verify first 2 digit 'gatekeeper' requirement is met */
            if(((chk_value/10 == 1)&&(chk_value % 2 == 0)) || ((chk_value/10 == 3)&&(chk_value % 10 == 1)))
            {
                /* number must be prime */
                if(isit_prime(result) == 1)
                {
                    while(power)
                    {
                        /* convert number to char values */
                        answer = lldiv(result, pow(10, power--));
                        buf[a][b++] = (answer.quot) ^ 48;
                        result = answer.rem;
                    }
                    buf[a][b] = (int)result ^ 48;
                    printf("%s\n", buf[a]);
                    a++; b = 0;
                }
            }

            x += skip_val[itr];
            y += skip_val[itr];
            cnt--;
            itr++;
        }
    }
   
    b = 0;
    x = 0;

    /* seach buf for reverse value in rev */
    for(x = 0; x < MAX_BUF; x++)
    {
        a = 0; b = strlen(buf[x]);

        while(b)
        {
            /* create a string in rev that is
             * the reverse of buf[][]
             */
            rev[a] = buf[x][b - 1];
            a++; b--;
        }

        a = 0;

        /* start comparison of buf and rev with
         * values of the same magnitude.
         */
        while(strlen(rev) > strlen(buf[a]))
            a++;
       
        /* if there is a reverse prime in buf it will be found
         * by searching all numbers in buf of the same magnitude
         */
        while(strlen(rev) == strlen(buf[a]) && ( a < MAX_BUF))
        {
            /* strcmp returns 0 if strings are equal */
            if(!strcmp(rev, buf[a]))
            {
                printf("\n%s\t%s\t%ld\n", buf[x], rev, x);
                break;
            }
            else
                a++;
        }
    }
     return 0;
}

/* returns 1 if prime is a prime. */
int isit_prime(long long prime)
{
    long long candidate, x;
   
    x = 3;
    candidate = prime;
       
    while(x <= sqrtl(candidate))
    {
        if(fmodl(candidate, x) == 0)
        {
            candidate++;
            break;
        }
        x += 2;
    }
     
    if(candidate == prime)
        return 1;
    else
        return 0;
}

/* returns the 2 highest magnitude digits (leftmost digits) of given number */
int magnitude(long long result, int *pwr)
{
    int b = 0;
    long long copy;
   
    /* structure lldiv_t contains ans.quot and ans.rem */
    lldiv_t ans;
   
    /* we need result later */
    copy = result;
   
    /*   Ptr to 'power' variable.     */
    /*   decrease because 10^0 = 1.   */
    *pwr = -1;

    while(copy)
    { 
        ans = lldiv(copy,10);
        copy = ans.quot;
       
        /* record numbers 10^nth power */
        (*pwr)++;
    }
    (*pwr)--;   /***    to isolate first 2 digits       ***/

    b = result/pow(10, *pwr);

    (*pwr)++;   /***    restore to proper magnitude     ***/

    return b;  /***    rtrns first 2 digits of number  ***/
}



I use the following program to verify 4n+1 fermat primes:

Code:

/**************************************************************************
* fermat.c                                               05.04.2009       *
*                                                                         *
* Program takes a positive value input by the user and determines if the  *
* number is prime or not.  If the number is NOT prime, the prime factors  *
* of the number are displayed.  If the number IS  prime the program does  *
* further processing to determine if the number is a  "4n-1" prime or if  *
* it is a  "4n+1" prime.  If the  number is the later  type, the program  *
* further determines which two whole numbers, when sqaured and added to-  *
* gether, equal the "4n+1" prime.                                         *
*                                                                         *
* compile = $> gcc -o fermat fermat.c -lm                                 *
**************************************************************************/
                                                                                                 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Function that determines 4n-1 or 4n+1 prime */
int chk_prime(long double, int *);

int main()
{
   long double x = 0;
   long double candidate, prime = 1;
     int prime_flag = 0;
     int *flag = &prime_flag;
   char in_str[30];
   char *end;       /* used by strtoll() */

   printf("\n\n");
   printf("\tThis program evaluates the number given for prime aspects\n");
   printf("\trelated to Fermat's 4n+1  theory.  Fermat states that any\n");
   printf("\t4n+1 type prime can  be expressed as the sum of two whole\n");
   printf("\tnumbers after they have been squared.\n\n");
   printf("\tIf the number given is a 4n+1 type prime the program will\n");
   printf("\treturn these  numbers.  Otherwise, if the number is not a\n");
   printf("\tprime the prime factors of the number are returned\n\n");

     while(prime)
     {
      /* uses strtoll()                             */
      /* to chk for chars 0-9. If valid input chars */
      /* are converted to long double value.        */
      printf("\n\n   Enter a positive integer: ");
      fgets(in_str, 30, stdin);                     
      candidate = strtold(in_str, &end);       

        prime = candidate;
        
        printf("\n\n   ");

      if((prime == 1)||(prime == 2))
        {
         printf("%.0Lf is a prime number", prime);
            candidate = 0;      
        }
      
      /* Used to prevent print statements after return from */
      /* the chk_prime function                             */
      prime_flag = 0;

      x = 2;

        while(x <= sqrtl(candidate))
        {
         while(fmodl(candidate, x) == 0)
         {
                if(candidate == x)
               /* Done factoring, bailout */
                break;
                else
                   printf("%.0Lf * ", x);

                candidate = candidate/x;
           }
               
         if(x == 2)
              x++;
         else
              x += 2;
        }

      /* To enter here we must have a prime */
      if((prime) && (candidate == prime))
            /* determine which type prime? */
             chk_prime(prime, flag);

        if(candidate == 1)
           printf(" are prime factors of: %.0Lf\n\n ", prime);
   
        if((!prime_flag) && (candidate))
        {
         printf("%.0Lf", candidate);
         printf(" are prime factors of: %.0Lf\n\n ", prime);
        }
   }
   return 0;
}

int chk_prime(long double prime, int *flag)
{
   long double x = 1;
   long double try;

   /* Go here if we have a 4n+1 prime */
   if((fmodl((prime - 1), 4)) == 0)
   {
      printf("%.0Lf is a \"4n + 1\" type prime that can be\n", prime);
      printf("   expressed as the sum of 2 whole numbers squared:");

      /* This while blk determines whole number squares of the prime */
      while(x++ < sqrtl(prime + 1))
      {
         /* try^2 == prime - x^2, so... */

         try = sqrtl(prime - (x * x));

         if((try - ((signed int)try)) == 0)
         {
            /* If here then the square root of try has 0 as a fractonal part   */
            /* which means try is a natural number. So try is one of the uni-  */
            /* que numbers and therefore variable 'x' has to be the other.     */

            printf("\n\n   %.0Lf^2 + %.0Lf^2 = %.0Lf\n\n", x, try, prime);
              break;
           }
      }
   }
   else
      printf("%.0Lf is a \"4n - 1\" type prime\n\n", prime);

   *flag = 1;
   return 0;
}