New Topic/Question
Reply
center squared primes (prime == sum of 2 consecutive whole numbers
squared). For instance:
12641 <====> 14621 is an emirp and:
12641 = 79^2 + 80^2
14621 = 85^2 + 86^2 are both center squared
I've written this code to generate emirp candidates but it is slow
and I have reached the limit of my c skills. I would appreciate
any help/suggestions/guideance on improving my program or trying a
better whole new approach. thanks
/* remirp.c 09.23.2012
*
* Program to generate prime numbers that are emirps and
* also may be a center squared emirp pair.
*
* Criteria:
* The emirp pair must both be center squared prime numbers.
* e.g. the emirp pair 12641 <===> 14621 are
* also center sq. prime numbers which are 4n+1 type primes
* where the sum of two CONSECUTIVE numbers squared = p.
* 12641 = 79^2 + 80^2
* 14621 = 85^2 + 86^2
*
* Strategy:
* It seems that when squaring consecutive whole numbers the
* sum always has a 1, 3 or 5 as the last digit. All sums end-
* ing with 5 can't be prime so that leaves 1 and 3. Further,
* if the last digit is 1 then it is always proceeded by zero
* or an even digit 2, 4, 6 or 8. If the last digit is 3 then
* it is always proceeded by a 1. The prog. checks all primes
* that start with 1[0,2,4,6,8] or 31 and have the last digits
* of [0,2,4,6,8]1 or 13.
*
* compile with $> gcc -o remirp remirp.c -lm
*
* last run with MAX_RANGE = 1 000 000 000 --> 22m41.497s 10/07/12
*
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX_RANGE 1000000
int main(void)
{
int x = 1;
int p = 101;
int p2 = 0;
int itr = 0;
int cnt = 0;
int rev = 0;
int low = 0;
int high = 0;
int power = 0;
int ndx_fwd = 0;
int ndx_rev = 0;
// lookup tables
int rev_lut[]={01,21,41,61,81,13};
int fwd_lut[]={10,12,14,16,18,31};
int skip_val[]={2,8,2,8,2,8,2,8};
while(p < MAX_RANGE)
{
cnt = 8;
itr = 0;
while(cnt--)
{
// check p for primeness.
if(isit_prime((long double)p))
{
p2 = p;
power = -1; // because 10^0 = 1
// reverse p
while(p2 > 0)
{
rev = rev * 10 + (p2 % 10);
p2 = p2/10;
// record nth power of 10
power++;
}
x = 1;
while(power--)
// depending on power, x = 100, 1000, 10000, 100000...etc
x *= 10;
// last 2 digits
low = p%100;
// first 2 digits
high = p/(x/10);
// these 3 if blocks use the 1st 2 digits of p
// to qualify p and if needed change p to avoid
// processing unqualified values of p. Changed
// values are all set to new value + 1 to stay
// in sync with skip_val[].
if((high%2)&&(high < 19))
{
// chg p to 1[2,4,6,8]000....+ 1
p=(p/(x/10));
p++;
p=(p*(x/10))+1;
cnt = 0; itr = 0; rev = 0;
continue;
}
else if((high > 18)&&(high < 31))
{
// chg p to 3100....+ 1
p=(x/10)*31;
p++;
cnt = 0; itr = 0; rev = 0;
continue;
}
else if(high > 31)
{
// chg p to next magnitude 1000....+ 1
p=(x*10)+1;
cnt = 0; itr = 0; rev = 0;
continue;
}
ndx_fwd = 0;
ndx_rev = 0;
// Are p and rev an emirp pair?
while(ndx_fwd < 6)
{
if(high == fwd_lut[ndx_fwd])
{
// if here we need look no further in fwd_lut.
ndx_fwd = 6;
while(ndx_rev < 6)
{
if(low == rev_lut[ndx_rev])
{
// If rev != p (palindrome) and rev is prime
if((rev ^ p)&&(isit_prime((long double)rev)))
printf("\n%d", p);
// get out of this while()
ndx_rev = 6;
}
ndx_rev++;
}
}
ndx_fwd++;
}
}
rev = 0;
p = p += skip_val[itr++];
}
}
return 0;
}
// returns 1 if prime is prime.
int isit_prime(long double prime)
{
long double candidate, x;
x = 2;
candidate = prime;
while(x <= sqrtl(candidate))
{
if(fmodl(candidate, x) == 0)
{
// Not prime...
// Change candidate to fail last if() below.
candidate++;
break;
}
if(x != 2)
x += 2;
else
x++;
}
if(candidate == prime)
return 1;
else
return 0;
}
MultiQuote
| 