# improve emirp generator

Page 1 of 1

## 2 Replies - 1392 Views - Last Post: 09 October 2012 - 09:54 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294987&amp;s=34a7cf31a4be06ea63471d00b3d5ea0e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 scurveedog

Reputation: 0
• Posts: 4
• Joined: 23-September 12

# improve emirp generator

Posted 09 October 2012 - 07:53 PM

I'm looking for emirps of a specific type where the emirp are also
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;
}

```

Is This A Good Question/Topic? 0

## Replies To: improve emirp generator

### #2 jimblumberg

Reputation: 4736
• Posts: 14,769
• Joined: 25-December 09

## Re: improve emirp generator

Posted 09 October 2012 - 09:31 PM

What do you consider slow? Your program takes about 2/10 of a second.

Jim

### #3 scurveedog

Reputation: 0
• Posts: 4
• Joined: 23-September 12

## Re: improve emirp generator

Posted 09 October 2012 - 09:54 PM

Hello Jim

on my computer an 8 yr. old toshiba p4 laptop it took 22m41.497s with MAX_RANGE set at 1,000,000,000.
I lowered MAX_RANGE to 1,000,000 for testing and that's what it is in the post. Sorry, I should have
pointed that out.

I just found a prime check algorithm on the snippets page of this site posted by retardedgenius that
is way faster than mine and I'm testing that right now.