# improve emirp generator

Page 1 of 1

## 2 Replies - 1380 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=d44db9a8bd1387c799a8fca387a0f4cd&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 scurveedog

• New D.I.C Head

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
Was This Post Helpful? 0

### #3 scurveedog

• New D.I.C Head

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.

Thanks for replying
Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }