Project Euler: Truncatable Primes

So, this is going to be a hard one to follow.. I believe it requires me to post all of my code in order to get the idea.. So if you have the time (or if you love me that much), I would appreciate it if you took a look at this.. Here's the original Problem 37. I have looked over my code several times and can't seem to discover my error. Well, here we go:

Code Java:

import java.util.*;
public class prob37 {
public static void main(String args[]){
int sum = 0;
ArrayList<String> list = new ArrayList<String>();
for(int i = 1000000; i > 100; i--){
for(int a = 0; a < list.size(); a++){
if(list.get(a).contains("" + i)){
i--;
}
}
if(allPrimeLeft(i) && allPrimeRight(i)){
System.out.println(i);
list.add("" + i);
sum+=i;
}
}
System.out.println(sum);
}
public static boolean isPrime(int n){
if(n%2==0)
return false;
for(int i = 3; i < Math.sqrt(n)+1; i+=2){
if(n%i==0)
return false;
}
return true;
}
public static boolean allPrimeLeft(int n){
if(!isPrime(n))
return false;
String s = "" + n;
for(int i = 0; i < s.length()-1;i++){
s = s.substring(1, s.length());
int temp = Integer.parseInt(s);
if(!isPrime(temp))
return false;
}
return true;
}
public static boolean allPrimeRight(int n){
if(!isPrime(n))
return false;
while(n > 0){
if(!isPrime(n))
return false;
n/=10;
}
return true;
}
}

If you looked over this, and got to this point, YOURE AWESOME! Haha, but I'm going to keep looking it over as well... Please comment back if you have any question over my code or have a pointer for me to follow.

__Output__:

739397

73331

31193

19739

7331

3797

3137

1997

1373

719

317

179

173

131

113

882927 ---> This is the Sum I receive.

There are only supposed to be 11 numbers, but I return 15. Also the correct Sum is 748317. Maybe we can work this through the output.

*Difference Between My Sum and The Actual Sum = 134610*

Re: Project Euler: Truncatable Primes

How can numbers that begin or end in a non-prime (like 9) be truncatable primes?

Re: Project Euler: Truncatable Primes

I don't think your isPrime() method works correctly... It won't return 2 as prime. It also returns 1 or 0 as being prime (technically they are not). I'm also not so sure your two AllPrime methods are correct, but I don't understand the algorithm you're using or read them over all that carefully.

Re: Project Euler: Truncatable Primes

Quote:

Originally Posted by

**KevinWorkman**
How can numbers that begin or end in a non-prime (like 9) be truncatable primes?

Wow, you can tell I was late up last night :| My *isPrime *method is working fine except that it counts 1 as a prime (it doesn't count 0 or 9 as a prime). There's something wrong with my *allPrimeLeft* method.

I'm going to entirely restart that method.. Is there a way to remove the leftmost digit until you reach the rightmost digit? I know if you had 1234, you could do 1234%1000, then do 234%100, etc... But that doesn't seem like the best possible solution.

Re: Project Euler: Truncatable Primes

Using mod seems like a perfectly reasonable approach. Or you could turn it into a String and manipulate it that way. Whatever fits into your head the best.

Re: Project Euler: Truncatable Primes

So, after fixing all the kinks.. *Corrected allPrimeLeft method and debugged to be sure... Took out ArrayList because it went against the prompt... Counted down to 10 instead of 100 when checking if the int i is a truncatable prime*

So here's my new output!

739397

3797

3137

797

373

317

313

73

53

37

748294 ---> Sum

*Difference between My Sum and Their Sum -> 23*

However, now I have 11 numbers... And they are all truncatable left and right.. I even double checked.. So, I'm entirely stumped.

Re: Project Euler: Truncatable Primes

I'm only counting 10 numbers. And I bet I can guess what number is missing.

Re: Project Euler: Truncatable Primes

Quote:

Originally Posted by

**KevinWorkman**
I'm only counting 10 numbers. And I bet I can guess what number is missing.

Shhh don't tell me! :)