题目链接：https://projecteuler.net/problem=41
这个数是由1到n的数组成，并且是质数，求这样的数的最大值。

在题解论坛中看到先根据这个数是几位数，判断能不能被3整除。

1+2+3+4+5+6+7+8+9=45，1-9组成的数能被3整除
1+2+3+4+5+6+7+8=36，1-8组成的数能被3整除
1+2+3+4+5+6+7=28，1-7组成的数不能被3整除
1+2+3+4+5+6=21，1-6组成的数能被3整除
1+2+3+4+5=15，1-5组成的数能被3整除
1+2+3+4=10，1-4组成的数不能被3整除
1+2+3=6，1-3组成的数能被3整除
1+2=3，1-2组成的数能被3整除
1

根据上面结果是质数、又是1-n的数组成的，只能是1-4组成的数，或者1-7组成的数。
这样，分布在两个范围内找最大的质数就好了。

问题是如何判断这数是由1到n的数字组成的，（n最大是9，根据上面分析只能是7或4）
我用的Java中的集合相等来判断的。
具体思路：
1.这个数包含0，或者长度大于等于10，都不满足
2.将这个数中的每位数字添加到集合中
3.每添加一个元素，再第二个集合中依次添加1到n的数字
4.在添加到集合的过程如何集合的大小不等于我们添加的次数，则不满足
5.判断两个集合是否相等
6.相等则是由1到n的数组成的

为了减少不必要的运算，有1到n组成的数很少，然而质数相对多，可以先判定是1到n的数在判断是不是质数。

还有个问题：能不能先求出这个1到n组成的数，再判断是不是质数

Java代码：

package projecteuler31to40;import java.util.Date;
import java.util.Set;
import java.util.TreeSet;class level41{  void solve(){long Max_Value=7654321;long Min_Value=1234567;int d=1;for(long i=Max_Value;i>2;i=i-2){if(isNDigit(i)){if(isPrime(i)){System.out.println("OK:"+i);break;}}}
// isPandigital(1234567,7654321);
// isPandigital(1234,4321);}void isPandigital(long min,long max){for(long i=max;i>=min;i=i-2){if(isNDigit(i)){if(isPrime(i)){System.out.println("Pandigital:"+i);}}}}boolean isNDigit(long num){String str=String.valueOf(num);Set set=new TreeSet();Set setEqual=new TreeSet();if(str.indexOf("0")>-1) return false;if(str.length()>=10) return false;for(int i=0;i<str.length();i++){set.add(str.substring(i,i+1));setEqual.add(String.valueOf(i+1));if(set.size()< (i+1)){return false;}}return set.equals(setEqual);}boolean isPrime(long num){for(long i=2;i<=Math.sqrt(num);i++)if(num%i==0)return false;return true;}}
public class Problem41 {public static void main(String[] args){Date beginTime=new Date();new level41().solve();Date endTime=new Date();long Time=endTime.getTime()-beginTime.getTime();System.out.println("Time:"+Time/1000+"s"+Time%1000+"ms");}}

结果：

OK:7652413
Time:0s39ms

Python代码：

def isPrime(num):if num in (1,4):return Falseif num in (2,3):return Truefor i in range(2,int(num**0.5)+1):if num%i==0:return Falsereturn Truedef getN_Set(n):digits=set()for i in range(1,n+1):digits.add(str(i))return digitsdef isN_Digit(num):p=str(num)if len(p)>=10:return Falseif p.find('0')!=-1:return Falsereturn getN_Set(len(p))==set(p)from time import time
t0=time()
for i in range(7654321,1234567,-2):if isN_Digit(i):if isPrime(i):print ibreak
t1=time()print t1-t0

结果：

7652413
>>> t1=time()
>>> 
>>> print t1-t0
2.81699991226

Python程序，也是根据Java的程序改写的，有很多相同的地方。

在题解论坛中看到下面的Python程序：

import itertools, mathdef isPrime(n):if n < 2:return Falseelif n < 4:return Trueelif n % 2 == 0 or n % 3 == 0:return Falsei=5for i in range(5,int(math.sqrt(n))+1,6):if n % i == 0 or n % (i + 2) == 0:return Falsereturn Truegen = [ int(''.join(p))  for p in itertools.permutations("7654321") ]for i in gen:if isPrime(i):print(i)break

根据程序可以看出：gen保存着所有的1到7的所有组合的数。

itertools 是个Python中的迭代器模块，有时间研究下。

上面判定质数与法四很类似。

根据Python可以直接求出了1到n组合的数，用Java等能不能写出来？
题解论坛有，也就是对1-n，n个数的所有排列形式，有A（n，n）种
脑容量不够，有时间再写。

插曲：关与质数的判断方法

法一：

boolean isPrime(long num){for(long i=2;i<num;i++)if(num%i==0)return false;return true;}

这个时间复杂度比较大：O(N)

法二：

boolean isPrime(long num){for(long i=2;i<=num/2;i++)if(num%i==0)return false;return true;}

这个之前一半，时间复杂度：O（N/2）

法三：

boolean isPrime(long num){for(long i=2;i<=Math.sqrt(num);i++)if(num%i==0)return false;return true;}

时间复杂度：O（sqrt（N））

这个我用的比较多，比上面两个节约好多时间的。
下面介绍的方法是在题解论坛中，看到老外用到的方法。

法四：

 boolean is_prime(int x){if (x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13)return true;if (x < 2 || x % 2 == 0)return false;for (int i = 3; i * i <= x; i++)if (x % i == 0)return false;return true;
}

看到好多根据这个写的判断是质数的，许多都是大同小异。
2 3 5 7 11 13，直接返回true
1 偶数，直接返回false
其他，与法三很类似，时间复杂度是：O（sqrt（N））

粗落估算平均时间复杂度：{ N/2的是1+N/2的是O（sqrt（N/2））}/N=O（sqrt（N/2））
比法三少了好多时间的。

欧拉工程第41题：Pandigital prime

插曲：关与质数的判断方法

法一：

法二：

法三：

法四：