2 Replies - 752 Views - Last Post: 09 October 2012 - 09:54 PM Rate Topic: -----

#1 scurveedog  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is online

  • member icon


Reputation: 3989
  • View blog
  • Posts: 12,307
  • 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  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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