Projecteuler.net – Problem 41 – Java

http://projecteuler.net/problem=41

Made use again of Lexicographic permutation so I put it in a class of its own. I also created a Prime class that checks if a number is prime. I kind of lucked out and didn’t have to check all the 1 to n pandigital possibilities. I started with 1 to 9 pandigital figuring the largest prime would be in there someplace. The program ran but didn’t spit out any results. I thought it was broken. The code looked right so I tried 1 to 8 pandigital. Nothing. 1 to 7 did output a result, and it was the correct answer. So, the code gets the right answer but doesn’t check all the possibilities now that I know that the largest prime is a 1 to 7 pandigital number.

This class holds the main.

public class Euler41 {

	public static void main(String[] args) {
		
		Boolean b;
		String num = "1234567";
		long largest = 0;
		
		Prime p = new Prime();
		p.setNumber(num);
		
		Lexicographic l = new Lexicographic();
		l.setNumber(num);
		
		while (l.getNumber() != "last") {
			b = p.isPrime();
			if (b == true) {
				if (Long.parseLong(p.getNumber()) > largest) {
					largest = Long.parseLong(p.getNumber());
				}			
			}
			l.setNumber(l.getNextPermutation());
			p.setNumber(l.getNumber());			
		}
		
		System.out.println(largest);

	}

}

This is my Prime class.

public class Prime {

	// the number we work with
	private String number;
	private Boolean isPrime;
	
	// number setter
	public void setNumber(String number) {
		this.number = number;
	}
	
	// number getter
	public String getNumber() {
		return number;
	}
	
	// Check if our number is a prime number
	public Boolean isPrime() {
		
		// start true
		isPrime = true;
		
		if (Long.parseLong(number) < 1) { isPrime = false; }
		if (Long.parseLong(number) == 1) { isPrime = true; }
		
		for (long i = 2; i <= Math.sqrt(Long.parseLong(number)); i++) {
			if (Long.parseLong(number) % i == 0) {
				isPrime = false;
				break;
			}
		}
		
		return isPrime;
	}
	
}

This is my Lexicographic class. Which should look familiar as I’ve used it before in similar form.

public class Lexicographic {

	// the number we work with
	private String number;
	
		
	// number setter
	public void setNumber(String number) {
		this.number = number;
	}
		
	// number getter
	public String getNumber() {
		return number;
	}	
	
	// Returns the next permutation in Lexicographic order
	public String getNextPermutation() {
					
		int largestIndexK = -1;			// if this stays negative, we are at last permutation
		int largestIndexL = 0;
		char[] b = number.toCharArray();		// holds the next permutation as we build it
		
		// Find the largest index k such that a[k] < a[k + 1]. 
		// If no such index exists, the permutation is the last permutation.
		for (int k = 0; k < number.length() - 1; k++) {
			if (number.charAt(k) < number.charAt(k + 1)) {
				largestIndexK = k;
			}		
		}
		
		// Last permutation
		if (largestIndexK == -1) {
			return "last";
		} 
		
		// Find the largest index l such that a[k] < a[l]. 
		// Since k + 1 is such an index, l is well defined and satisfies k < l.
		for (int l = 0; l < number.length(); l++) {
			if (number.charAt(largestIndexK) < number.charAt(l)) {
				largestIndexL = l;
			}
		}
						
		// Swap a[k] with a[l]. 
		b[largestIndexK] = number.charAt(largestIndexL);
		b[largestIndexL] = number.charAt(largestIndexK);
				
		// Reverse the sequence from a[k + 1] up to and including the final element a[n].
		String s = new String(b).substring(largestIndexK + 1);		
		int x = 1;
		for (int i=s.length(); i > 0; i--) {
			b[largestIndexK + x] = s.charAt(i - 1);			
			x++;			
		}
		
		String nextPermutation = new String(b);		
				
		return nextPermutation;
		
	}
	
}
This entry was posted in Java, Project Euler. Bookmark the permalink.

Leave a Reply