Problem 41

问题描述：

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

解决问题：

 

这题和Problem24差不多。都是全排列的问题。

不过这里我们得找到所有的排列数字。然后判断是否是素数。

P24是让我们找到第n个排列，我们可以从1一直找到最后一个~

不过使用24的方法肯定是不行的。

 

最好的方法就是从小到大挨个找。

 

这里使用递归的方法。

假如找到4位数的全排列,n4n3n2n1

先令初始的可以选择的数为{1,2,3,4}

令n1=1，则n2只能在{1,2,3,4}-{1} = {2,3,4}的集合里找

再n2=2，则n3只能在{2,3,4}-{2}={3,4}的几个里找

 

 

算法：

public static void find(int level, boolean[] elements, long result) {

		if (level == 1) {
			if(IsPrime(result)){
				if(max<result)
					max = result;
			}
//			System.out.println(result);
			return;
		}
		for (int i = 1; i < elements.length; i++) {
			if (elements[i]) {
				elements[i] = false;
				long tmp = result;
				result = result * 10 + i;
				find(level - 1, elements, result);
				elements[i] = true;
				result = tmp;
			}
			// System.out.println("Level:"+level+",i:"+i+",Result:"+result);
		}
	}