Step Ten  Emirps

Design a program called emirps.cpp which will identify all of the emirps between two positive integers N1 and N2 exclusively. We will assume N1 < N2.

An emirp is a prime which is also a prime when all of its digits are reversed, excluding palindromic primes. For example, 13 and 17 are emirps because 31 and 71 are also prime. The prime number 131 is not an emirp because it is palindromic.

So, the idea is, find the first prime after N1, reverse it, then determine if the reversed number is also prime. Continue this until you reach N2.

You might try to do this top down.

  1. Imagine a loop variable ii from N1+1 up to N2-1
  2. Imagine you have a boolean function called prime with an integer parameter (the prime candidate) which returns true if the integer parameter is a prime number
  3. Imagine you have an integer function called reverse with an integer parameter (the number you want to reverse) which returns the input number reversed.
  4. With these three imaginary building blocks, the program is just:
    for ii = (N1 + 1) up to (N2 - 1)
      if prime(ii) and prime( reverse(ii) ) and ( ii != reverse(ii) ) print out ii
    end for
  5. Now build the loop and stubs for prime and reverse.
  6. Get prime working and test it out.
    The prototype for the function is:
    bool prime(int number);
    The pseudocode for this function is:
    set isprime equal to true
    set divisor equal to two
    while divisor is less than number and isprime is true
      if divisor goes into number evenly, set isprime equal to false
      increment divisor by one
    end while
    return isprime
  7. Get reverse working and test it out.
    The prototype for the function is:
    int reverse(int number);
    The pseudocode for this function is:
    set total equal to zero
    set digits equal to one
    figure out how many digits there are in the number:
      while (int(number / pow(10, digits)) != 0 ) ++digits
    for ii equal to 1 up to ii equal to digits
      add (number % 10)*pow(10,digits - ii) to total
      divide number by 10 and store the result back in number
    end for
    return total
  8. Put it all together

Advance to Step Eleven

Return to the Table of Contents