Prime Palindromes

/*

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();   
}

#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);
}

#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();
}

/* 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  ***/
}

/**************************************************************************
* 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;
}