Thread: Right-prime number algorithm problem

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    2

    Right-prime number algorithm problem

    I'm having trouble developing an algorithm to check if a prime number is also right-prime. A right-truncatable prime number (or right-prime number) is a prime number that remains prime as each of it's right-most digits is removed. For example, consider the value 719. 719 is prime, 71 is prime, and 7 is prime, so the value 719 is a right-prime number.

    Supposedly this should be a very simple algorithm, but I don't even know where to begin. All I really need help with is pseudocode. I can do the syntax on my own once I figure out the correct algorithm.

  2. #2
    Registered User
    Join Date
    Aug 2008
    Location
    Belgrade, Serbia
    Posts
    163
    Well, what's the problem? Determining if a number is prime or removing the digits?
    Vanity of vanities, saith the Preacher, vanity of vanities; all is vanity.
    What profit hath a man of all his labour which he taketh under the sun?
    All the rivers run into the sea; yet the sea is not full; unto the place from whence the rivers come, thither they return again.
    For in much wisdom is much grief: and he that increaseth knowledge increaseth sorrow.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    2
    I can already determine if it is prime, I just need help removing the digits.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    First, you'll need to get the input on the number (file, user, etc.). Then perhaps check whether the number is in fact, a prime. For that checking you'll either need an array of primes in your program already, or you'll need to calculate your primes and keep them in an array.

    Calculating primes is very quick and easy, but if an array of primes already calculated is OK, then that's even easier to do.

    Now you're ready to, while the number to be checked is greater than zero, assign the modulo (remainder) of 10, (use the % operator), to an integer variable. That's the right most digit. Now divide the number by 10, and you can test the new (smaller) number and see if it's prime.

    It's easier to program that to describe, and shorter as well, so give that a try.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    If you're good with C syntax, then giving you pseudo code is basically like giving you real code, which violates our homework policy. IMO, problem solving is far more important to being a good programmer than "doing the syntax" is. After 10 years, I still leave off semicolons, forget to escape the occasional character, or have to go look up operator precedence or associativity. The compiler can catch those errors, or I can look it up minutes in one of the dozens of books or web pages that covers C. Problem solving, however, can not just be looked up, or an erroneous line pointed out by the compiler. Also, it transfers between all languages, and thus to any programming job or assignment. It a far more important skill to hone.

    But good thing for you, you already know how to solve this. You just don't realize it yet. The example you provided shows the process. I suggest you work out several examples by hand on paper, some that are right-prime, some that aren't prime, and some which start out right-prime, but fail part way through (e.g. 3373 is prime, 337 is prime, 33 is not). This Wikipedia page has lists of right-prime numbers for you to use.

    Then come back and take a stab at the pseudo code. Even if you can't get pseudo code up, try explaining in plain English the process you are going through to determine if a number is right-prime. Then we'll guide you.

    EDIT: I see the others beat me to it, and that your actual problem was stripping off the numbers, not the general algorithm.

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by shufu7-11 View Post
    I can already determine if it is prime, I just need help removing the digits.
    Wellllll... you could try dividing by ten.

    Code:
    int x = 719;
    
    while(x > 0 )
      { printf("%d\n",x);
         x /= 10; }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime number algorithm
    By Akkernight in forum C Programming
    Replies: 9
    Last Post: 04-19-2009, 01:50 PM
  2. Prime number problem
    By Antigloss in forum C Programming
    Replies: 13
    Last Post: 06-04-2005, 02:56 AM
  3. Replies: 3
    Last Post: 03-29-2005, 04:24 PM
  4. prime number algorithm
    By Unregistered in forum C++ Programming
    Replies: 12
    Last Post: 02-22-2002, 11:30 PM
  5. Prime Number problem
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 10-08-2001, 08:00 PM