Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: Project Euler: Truncatable Primes

  1. #1
    Member Staticity's Avatar
    Join Date
    Jul 2011
    Location
    Texas
    Posts
    105
    My Mood
    Inspired
    Thanks
    3
    Thanked 5 Times in 5 Posts

    Default 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:

    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
    Last edited by Staticity; October 10th, 2011 at 03:53 AM.
    Simplicity calls for Complexity. Think about it.


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,610
    My Mood
    Hungover
    Thanks
    145
    Thanked 658 Times in 563 Posts

    Default Re: Project Euler: Truncatable Primes

    How can numbers that begin or end in a non-prime (like 9) be truncatable primes?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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.

  4. #4
    Member Staticity's Avatar
    Join Date
    Jul 2011
    Location
    Texas
    Posts
    105
    My Mood
    Inspired
    Thanks
    3
    Thanked 5 Times in 5 Posts

    Default Re: Project Euler: Truncatable Primes

    Quote Originally Posted by KevinWorkman View Post
    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.
    Simplicity calls for Complexity. Think about it.

  5. #5
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,610
    My Mood
    Hungover
    Thanks
    145
    Thanked 658 Times in 563 Posts

    Default 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.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  6. #6
    Member Staticity's Avatar
    Join Date
    Jul 2011
    Location
    Texas
    Posts
    105
    My Mood
    Inspired
    Thanks
    3
    Thanked 5 Times in 5 Posts

    Default 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.
    Simplicity calls for Complexity. Think about it.

  7. #7
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,610
    My Mood
    Hungover
    Thanks
    145
    Thanked 658 Times in 563 Posts

    Default Re: Project Euler: Truncatable Primes

    I'm only counting 10 numbers. And I bet I can guess what number is missing.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  8. #8
    Member Staticity's Avatar
    Join Date
    Jul 2011
    Location
    Texas
    Posts
    105
    My Mood
    Inspired
    Thanks
    3
    Thanked 5 Times in 5 Posts

    Default Re: Project Euler: Truncatable Primes

    Quote Originally Posted by KevinWorkman View Post
    I'm only counting 10 numbers. And I bet I can guess what number is missing.
    Shhh don't tell me!
    Simplicity calls for Complexity. Think about it.

Similar Threads

  1. [SOLVED] isPrime Boolean Method returns true for squares of primes
    By Staticity in forum What's Wrong With My Code?
    Replies: 0
    Last Post: September 30th, 2011, 12:46 AM
  2. Printing Sum of Primes of a number
    By CodeNewb in forum What's Wrong With My Code?
    Replies: 9
    Last Post: July 12th, 2010, 02:25 PM
  3. Euler integration
    By Kakashi in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 2nd, 2009, 04:19 PM
  4. Calculate primes help
    By TommyFiz in forum What's Wrong With My Code?
    Replies: 3
    Last Post: October 28th, 2009, 12:41 AM
  5. Project Euler
    By helloworld922 in forum The Cafe
    Replies: 5
    Last Post: September 9th, 2009, 03:51 PM