Deletable Numbers Algorithm

[Analysk]

Hello,
I've been working on a project today regarding Deletable Numbers.
Basically the objective is that given an interval (say, [5000, 9000]), a sum of all the deletable numbers should be given.

I've written some code to determine all prime numbers within an interval (I made some tests and it calculated all primes within [1, 10000000] in 500ms), however even though I've been thinking about it all day, I have absolutely no idea on how to calculate which prime numbers are deletable.

Is there any algorithm for such an end? If not, any helpful ideas? =/

Thanks in advance.

[olivthill2]

"Deletable Numbers"? I guess you mean "Deletable Prime Numbers", such as they are described at http://www.primepuzzles.net/puzzles/puzz_138.htm

Maybe you could:
1: Find every prime number in your interval
2: For each one, have a loop on its digits
3: In the loop, remove one digit and see if you have a prime number again
4: If yes, then have a recursive call to step 2:.
5: If no, then your number if not a deletable prime number.

[Analysk]

"Deletable Numbers"? I guess you mean "Deletable Prime Numbers", such as they are described at http://www.primepuzzles.net/puzzles/puzz_138.htm

Maybe you could:
1: Find every prime number in your interval
2: For each one, have a loop on its digits
3: In the loop, remove one digit and see if you have a prime number again
4: If yes, then have a recursive call to step 2:.
5: If no, then your number if not a deletable prime number.

Yeah, sorry for the typo I meant Deletable Prime Numbers, of course.

And that was my implementation after I made the post. However since this thing has a maximum interval of [1, 12000000] and needs to run in less than 6 seconds for over 80 tests, testing each prime with recursion is probably not a very good idea. If only Java wasn't so freaking slow and high-level.
That because if I wanted to test all digits I'd have to cast it to a String, which is an extremely slow process. Or do you know of any faster way to go through all digits?

[Analysk]

Yeah, sorry for the typo I meant Deletable Prime Numbers, of course.

And that was my implementation after I made the post. However since this thing has a maximum interval of [1, 12000000] and needs to run in less than 6 seconds for over 80 tests, testing each prime with recursion is probably not a very good idea. If only Java wasn't so freaking slow and high-level.
That because if I wanted to test all digits I'd have to cast it to a String, which is an extremely slow process. Or do you know of any faster way to go through all digits?

Doesn't this forum have an Edit button for posts? =/

I wanted to add that it would still be slow if every value was calculated only once, or if I pre-calculated all values at the start.

[Zachm]

The following will parse a non negative integer into it's digits without conversion to string (C# code, java should be very similar):

List<int> getDigits(int nonNegativeInt)
{
List<int> digits = new List<int>();

do
{
digits.Add(nonNegativeInt % 10);
nonNegativeInt = nonNegativeInt / 10;
}
while (nonNegativeInt > 0);

return digits;
}


I hope this will help increase the performance.

Regards,
Zachm