小练习：20161017 最大的n位pandigital质数是多少？

冬雪雪冬 · 发表于 2016-10-17 10:00:00

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-10-24 09:59 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

登录/注册后可看大图

好了言归正传，我们开始做小练习。

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即10.24 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----回帖需写明解题思路，鼓励在程序中加上注释-----
----除列出程序外，请给出输出的结果。----

题目：

如果一个数字将 1 到 n 的每个数字都使用且只使用了一次，我们将其称其为一个 n 位的 pandigital 数。例如，2143 是一个 4 位的 pandigital 数，并且是一个质数。

最大的 n 位 pandigital 质数是多少？

jerryxjr1220 · 发表于 2016-10-17 11:05:00

本帖最后由 jerryxjr1220 于 2016-10-17 14:02 编辑

这题其实有好多解法，我也想正好借这题，分享一些使用python解决一些数学题的心得。
【版主，在比赛结束后，如果觉得这篇经验分享还实用的话，希望能申请精华，让更多的鱼油看到，毕竟也花了我好些时间写的！@小甲鱼 @冬雪雪冬】
主要是针对没有任何算法基础的鱼油，算法高手可以直接跳过。

首先，从解题思路开始吧：
1. 最简单粗暴的方法，当然是暴力解法，就是从1开始依次往上增加，最大值当然是987654321，因为超过这个值就没法构成Pandigital了。
a）用暴力解法获取候选数
b）有了候选数以后就依次判断每个数，是否是Pandigital
i）候选数判断法：判断方法其实很简单，只要候选数中从1~n没有重复的数字即是Pandigital （举例：可以利用函数set（）函数及len（）把候选数列化为元组，再判断元组长度是否与原来相同，如果有重复的，长度必然会不同。）
ii）Pandigital直接生成法：直接生成的Pandigital数列可以省去判断的步骤，节省计算时间，后面介绍
c）有了Pandigital数以后就要判断是否是质数（质数的定义是：除了可以被1和自己本身整除以外，不能被其他自然数整除的数）
质数的判断方法也有很多：
i）暴力解法，同样使用从2开始的（1可以不用尝试，因为任何自然数必然能被1整除）自然数依次与候选数相除，上限是比本身小1的整数。如果中间没有任何一个数能与之整除，则即是质数，不然就不是（不是质数的自然数就是合数（除1以外））。
ii）优化算法1：候选数范围优化，后面介绍
iii）优化算法2：表格标记法优化，后面介绍
iv）其他优化算法：后面介绍
d）判断完质数以后，如果是质数，则保存起来后续要比较大小，如果不是则废弃。
比较大小其实也有不同的方法，而且所用时间也各不相同。
i）函数法：直接用max（）或min（）函数，求最大最小值。优点：简单，但如果候选数非常多的话，速度也不快（因为它的原理也是依次比较，然后判断）
ii）标记法：直接在计算过程中标记出最大值或最小值，这样只要计算完最大或最小值就出来了，不用额外计算时间。
iii）后排序法：用sort（）或者sorted（）对运算的结果排序后，那么第一个或者最后一个就是最大最小值。
iv）前排序法：用sort（）或者sorted（）对运算之前的候选数排序，那么这样只要在运行过程中第一个满足运算条件的数，就是要找的最大或最小值，后面的其他候选数都不用计算了。
做完，这么多步骤以后，我们终于得到我们需要的答案了。
2. 当然，你完全可以按照（1.）中描述的暴力解法的思路进行解题，而且只要思路正确，有足够时间，肯定能计算出结果。
但是，我要说的当然远不是这样。如果全部用上述的暴力解法解这题估计得花上几天（说不定几周）的时间来运行程序，这当然不是我们所希望的。
那么，我们就需要对上述的暴力解法进行优化了。（其实上述暴力解法的每个步骤都可以优化，我会逐步说明。）
a）候选数的优化
要判断候选数是不是Pandigital，最快的方法，当然是直接生成Pandigital啦，这样根本都不需要判断

所以，我用了Pandigital的生成法。生成法也有不同的方式，我写了2种不同的方案。
第一种是利用python的itertools库的函数permutations，生成排列组合。优点是程序简单。

from itertools import permutations as per
def getPan1(n):
pan = per(range(1,n+1),n)
panlist = []
for each in pan:
ee = 0
for e in each:
ee = ee*10 + e
panlist.append(ee)
return panlist

复制代码

第二种是用插入法，自己写的生成程序，运用了递归算法。

def getPan2(n):
if n == 2:
return [12,21]
if n>2:
pan = getPan2(n-1)
length = len(str(pan[0]))
pannew = []
for each in pan:
pannew.append(int(str(n)+str(each)))
pannew.append(int(str(each)+str(n)))
for j in range(1,length):
pannew.append(int(str(each)[:j]+str(n)+str(each)[j:]))
return pannew

复制代码

两种算法各有利弊，对于本题来说，差异并不是太明显，但是对于大数量的排序的话，差异会越来越明显。
b）质数判断优化
有了候选数以后就要判断质数了。
i）候选数的范围优化
其实，我们不需要把每个候选数都拿去和比候选数小的自然数相除来判断是否是质数。
质数有几个特性：
> 除了2以外，能被2整除的都不是质数（废话）。这样就可以砍掉一半的候选数了。
> 除了2和3以外的质数必然符合6k+/-1（k为自然数），这样又减少了1/6的数量。
> 而在相除时，只需相除到n**0.5（即根号n）即可，不需要全部除到完，这样再减少3/4的工作量。

def isPrime1(num):
if num == 2 or num ==3:
return True
elif num%2 == 0:
return False
elif (num-1) % 6 != 0 and (num+1) % 6 != 0:
return False
else:
for i in range(3,int(num**0.5+1),2):
if num%i == 0:
return False
return True

复制代码

ii）表格标记法优化
这种方法是先建立一个“空”的表格，然后依次把可能的项填入，或把不可能的项移除。标记法往往可以和递归算法套用，运用递归算法的便捷，加上标记法的高效记录。（纯用递归算法的话，往往效率很低，特别是嵌套层数很深的情况。）
在这里例子中，我是先建立了一个全为True的表格，然后依次把能除净的数（还包括0和1）对应的空格标记为False，那么剩下的就都是质数了。表格的index和表格的值，可以用enumerate（）函数联系起来。另外，表格的范围也只需到n**0.5的大小即可。

def getPrime(n):
primes = [True]*n
primes[0], primes[1] = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes[j] = False
primelist = []
for (k, trueprime) in enumerate(primes):
if trueprime:
primelist.append(k)
return primelist
primes = getPrime(10001)
def isPrime2(num):
if num in primes :
return True
elif (num-1) % 6 != 0 and (num+1) % 6 != 0:
return False
else:
for eachprime in primes:
if num % eachprime == 0:
return False
return True

复制代码

iii）其他算法优化
其实，上述的优化算法都可以相互结合，取长补短，根据不同的情况灵活调用。
通过这些性质的优化后，所剩的候选数已经足够可以被我们日常的计算机所应付了。
c）比较大小数的优化
在取得了是质数并且是Pandigital的数以后，最后一步就是取得这些值中的最大值
上面提的的函数法、标记法和后排序法，其实都是属于后运算的算法。这些算法都是要运算并且比较所有的候选数。
那么，有没有前运算的算法呢？答案是有的，前排序法就是前运算的算法。
这种算法的好处是，一旦得到第一个符合条件的值以后，后续的数值就不需要再运算了，可以节省大量时间。同时也省去了保存候选数的麻烦，因为根本都不需要保存。
方法就是：用sort（），reverse（）或者sorted（），reversed（）对运算之前的候选数排序，那么这样只要在运行过程中第一个满足运算条件的数，就是要找的最大或最小值，后面的其他候选数都不用计算了。

for k in range(9,1,-1):
testpan = reversed(getPan1(k))
for eachpan in testpan:
if isPrime1(eachpan):
print (eachpan)
end = time()
print ('Use: %.3f sec.' % (end-start))
exit()

复制代码

3. 结果

7652413
Use: 0.405 sec.

复制代码

这个就是运行的结果，我使用的是getPan1（）及isPrime1（）的方法。大家可以自行调试不同方法的差异。基本上这几种方法都是很快速的，都可以控制在0.5秒以内完成。这样，我们就把一个程序从原本可能要运行几天的时间，缩短到毫秒级的单位，这都是算法的功劳。
源代码如下：

from itertools import permutations as per
from time import time
start = time()
def isPrime1(num):
if num == 2 or num ==3:
return True
elif num%2 == 0:
return False
elif (num-1) % 6 != 0 and (num+1) % 6 != 0:
return False
else:
for i in range(3,int(num**0.5+1),2):
if num%i == 0:
return False
return True
def getPan1(n):
pan = per(range(1,n+1),n)
panlist = []
for each in pan:
ee = 0
for e in each:
ee = ee*10 + e
panlist.append(ee)
return panlist
for k in range(9,1,-1):
testpan = reversed(getPan1(k))
for eachpan in testpan:
if isPrime1(eachpan):
print (eachpan)
end = time()
print ('Use: %.3f sec.' % (end-start))
exit()

复制代码

我主要想通过这个例子告诉大家，其实，编程语言固然重要（Python是个非常好的工具，感谢小甲鱼的视频课程，我目前学习了1个月的时间，收益匪浅！），但是一个合理的算法往往比编程语言本身更重要。不要看几个毫秒好像和几秒差别不大，但是如果放到大数量级的地方，往往就是算得出和算不出的差别。
最后，我想说，算法其实没有好坏之分，只有合适和不合适之别。暴力算法确实是最“笨”的办法，但是当你一头雾水、毫无头绪的时候，暴力算法往往是最直接有效的算法，而且不需要特别高深的数学知识，只需要把描述变成计算机语言即可（对数据量不是特别大的情况都适用）。
感谢大家耐心看完本篇，我的程序也不是最优的程序，还有多种方法可以继续优化下去。但是对于本题来说，应该足够了。

富友郑鹏展 · 发表于 2016-10-17 15:09:48

本帖最后由富友郑鹏展于 2016-10-18 15:36 编辑

本程序使用Python2

# # coding=utf-8
# coding=utf-8
import time
import math as m
# 判断一个数是否是质数
def prime_number(n):
for i in xrange(2, int(m.sqrt(n))+1):
if n % i != 0:
continue
else:
return False
else:
return True
# 判断每个位数是否重复
def num_repeat(n):
str_num = str(n)
for i in str_num:
if str_num.count(str(i)) == 1:
continue
else:
return True
else:
return False
# 判断每个位数是否连续
def bit(n):
str_num = str(n)
b = len(str_num)
for i in xrange(b):
if str(i+1) in str_num:
continue
else:
return False
else:
return True
# 找出最大的pandigital数
# 由于3的倍数的特点，所有8位数和9位pandigital数都不是质数，所以从7位数开始找
num = 7654321
num_list = []
start = time.time()
while num > 0:
if num % 2 != 0 and num % 3 != 0 and num % 5 != 0:
if num_repeat(num) is False:
if bit(num) is True:
if prime_number(num) is True:
print '最大的pandigital质数是:%s' % num
break
else:
num -= 1
else:
num -= 1
else:
num -= 1
else:
num -= 1
print 'use time:%s s' % (time.time() - start)

复制代码

结果：

499573465 · 发表于 2016-10-18 12:46:39

from time import time
start=time()
save=[];N=1
def calculation(i): #判断是否为n位的 pandigital 数
j=1;
x=str(i)
while j<=len(x):
p=str(j)
a=x.count(p)
if (a!=1) or ('0'in x):
break
j+=1
if j==(len(x)+1):
return 1
else:
return 0
def judge(N): #判断是否为质数
k=2
while k<=int((N**0.5)+1):
if N%k==0:
break
k+=1
if k==(int((N**0.5)+1)+1):
return 1
else:
return 0
while N<=7654321: #8为和9位的pandigital数，必能被3整除，不是质数
if calculation(N) :
if judge(N):
save.append(N)
N+=1
print(max(save))
print('time=%f'%(time()-start))

复制代码

结果：

7652413
time=10.644090

复制代码

bacon6581 · 发表于 2016-10-18 17:24:45

本帖最后由 bacon6581 于 2016-10-22 02:23 编辑

前言：
最大的pandigital数当然是9位了，而且是且仅是987654321
于是我就第一位先取9、再取8....
第二位先取去掉第一位里的最大值，再取第二大的...
......
结果发现没有结果，校对了几次，还是没有结果....
再看题：n 位的 pandigital 数，原来n不一定等于9
----------------------------------------------------------------
那就当是8位，试了下，还是没有结果
再试7位，出来结果了7652413
后来一分析：
1+2+3+4+5+6+7+8+9能被3整除，也就是任意组合必能被3整除
1+2+3+4+5+6+7+8也能被3整除
直接只写7位数，不停的组合，然后判断是否质数，觉得不是很好
因为我已知结果是7位数了，如果一开始不知道是7位数，应该考虑其他位数的组合
花了半天的时间改进了下代码，从51行起，修改了代码
51行往上的，懒得改了！
-----------------------------------------------
0、先求出一批质数（2，987654321**0.5）之间的，用来快速判断组合是否质数
1、组合中数字之和能被3整除的，直接跳过，且舍弃该组合的最大一位数
如：【1、2、3、4、5、6、7、8】能被3整除，就不考虑它们的组合了，
舍掉最大值8，考虑【1、2、3、4、5、6、7】的组合
2、先求出该组合的长度，如【1、2、3、4、5、6、7】的长度为7
3、第一位有'组合的长度'种方式，7种
4、第二位有'组合的长度-1'种方式，6种
5、第三位有'组合的长度-2'种方式，5种
.......
6、判断该组合是否质数，如果是质数，跳出多重循环
7、输出结果
---------------------------------------------------------------
这题学到的内容：
1、python里没有goto语句，百度里找了个跳出多重循环的方法
2、复制列表，不能简单用“=”来赋值

代码如下：

from time import time
start = time()
class goto(Exception):pass
zs_max=987654321**0.5
zs=[2]
x=2
def zhishu(x):
zs_m=x**0.5
for i in zs:
if i>zs_m:
return True
if x%i==0:
return False
while x<zs_max:
x+=1
if zhishu(x)==True:
zs.append(x)
shu=[10,9,8,7,6,5,4,3,2,1]
try:
while 1:
shu.remove(shu[0])
jj=0
for j in shu:
jj+=j
if jj%3==0:
shu.remove(shu[0])
shu.remove(shu[0])
ln=len(shu)
for s1 in range(0,ln):
shu1=shu[:]
result1=shu1.pop(s1)*100000000
for s2 in range(0,ln-1):
shu2=shu1[:]
result2=result1+shu2.pop(s2)*10000000
for s3 in range(0,ln-2):
shu3=shu2[:]
result3=result2+shu3.pop(s3)*1000000
for s4 in range(0,ln-3):
shu4=shu3[:]
result4=result3+shu4.pop(s4)*100000
for s5 in range(0,ln-4):
shu5=shu4[:]
result5=result4+shu5.pop(s5)*10000
if ln<7:
result8=result5/1000+shu5[0]
print(result8)
print(shu5)
if zhishu(result8)==True:
result=result8
raise goto()
else:
for s6 in range(0,ln-5):
shu6=shu5[:]
result6=result5+shu6.pop(s6)*1000
if ln<8:
result8=result6/100+shu6[0]
if zhishu(result8)==True:
result=result8
raise goto()
else:
for s7 in range(0,ln-6):
shu7=shu6[:]
result7=result6+shu7.pop(s7)*100
if ln<9:
result8=result7/10+shu7[0]
if zhishu(result8)==True:
result=result8
raise goto()
else:
for s8 in range(0,ln-7):
shu8=shu7[:]
result8=result7+shu8.pop(s8)*10+shu8[0]
if zhishu(result8)==True:
result=result8
raise goto()
except goto:
pass
print(result)
print(time()-start)

复制代码

>>> ================================ RESTART ================================
>>>
7652413.0
0.8639051914215088
>>>

复制代码

小剑剑 · 发表于 2016-10-18 17:57:26

本帖最后由小剑剑于 2016-10-18 18:01 编辑

从大到小产生pandigital数检验是否为质数

from time import time
from itertools import permutations
from math import sqrt
time1,if_find=time(),False
def is_prime(num):#判断是否质数
if num<=1:
return False
else:
for i in range(2,int(sqrt(num))+1):
if not (num%i):
return False
return True
def tupletoint(j):#把一个元组中的数字合成一个数字
le=len(j)
i=0
su=0
while i<le:
su=su*10+j[i]
i+=1
return su
for i in range(9,0,-1):#这里的 i 是题中n
itertuple=permutations([ii for ii in range(i,0,-1)],i)#产生pandigital数
for j in itertuple:
num=tupletoint(j)
if is_prime(num):
time2,if_find=time(),True
print(num,time2-time1)
break
if if_find==True:
break

复制代码

答案7652413

wangzhenas · 发表于 2016-10-18 18:14:12

本帖最后由 wangzhenas 于 2016-10-23 21:06 编辑

答案： 7652413
耗时：0.11000633239746094

思路是用range生成（1-n）的一个序列，然后用permutation生成所有排列，再这里只需要考虑到7位置，因为所有1-8，1-9组成的序列都能被3整除
reduce函数将比如[1,2,3,4]的序列生成为一个整数
最后用filter筛选出符合条件的质数并max出最大值

from math import sqrt
from itertools import permutations
from functools import reduce
from time import time
t = time()
def is_prime(num):
for n in (2,3,5):
if num%n == 0:
return False
for n in range(7,int(sqrt(num))+1,2):
if num%n == 0:
return False
return True
print(max(filter(is_prime,(reduce(lambda x,y: 10*x + y,num)
for i in range(5,7+1)
for num in permutations(range(1,i+1)))
)),time()-t)

复制代码

hvagab · 发表于 2016-10-19 10:37:07

import time
st=time.time()
def pr(n):#定义一个质数判断函数
if n==2:return True
for j in range(2,int(n**0.5)+1):
      if n%j==0:
         return False
return True

#pandigital数最大位是九位但是8,9位pandigital数都能被3整除所以最高位质数是7位数
for i in range(7654321,1000,-1):
s=sorted('1234567')
if pr(i) and sorted(str(i))==s:#判断i的质数性和 pandigital性
      print(i)
      break
print(time.time()-st)

#输出
#7652413
#0.125

飘飞的白杨 · 发表于 2016-10-19 13:07:41

有数学知识可得，9位，8位的pandigital数不可能是素数
故直接从7位开始判断

from itertools import permutations as per
def prime(n): #判断素数
if n <= 1: return False
if n == 2: return True
for i in range(2,int(n**0.5)+1):
if n%i == 0: return False
return True
num = lambda i: i[0]*1000000+i[1]*100000+i[2]*10000+i[3]*1000+i[4]*100+i[5]*10+i[6] #由元组生成pandigital数字
for i in per([7, 6, 5, 4, 3, 2, 1]): #生成pandigital数
n = num(i)
if prime(n):
print(n)
break

复制代码

答案：7652413

lovesword · 发表于 2016-10-21 13:18:39

#! usr/bin/python
# -*- coding:utf-8 -*-
#python 2.7
import itertools,math
def isPrime(n):
if n == 1:
return False
elif n < 4:
return True
elif n & 1 == 0:
return False
elif n < 9:
return True
elif n %3 == 0:
return False
else:
r = math.floor(math.sqrt(n))
f = 5
while f <= r:
if n % f == 0:
return False
if n %(f+2) == 0:
return False
f += 6
return True
n = input('input n (n>1):')
if str(n).isdigit() and int(n)>1:
n = int(n)
tmp =list(itertools.permutations(xrange(1,n+1),n))
#tmp = map(lambda x:int(''.join(map(str,x))),tmp)
max_ = None
for i in tmp:
num = int(''.join(map(str,i)))
#print num
max_ = [max_,max(max_,num)][isPrime(num) is True]
print max_
else:
print 'n is not a int or n is <= 1'

复制代码

'''
========== RESTART: C:\Users\Administrator\Desktop\pycode\hosts.py ==========
input n (n>1):4
4231
>>>
input n (n>1):7
7652413
>>>
'''

Tid · 发表于 2016-10-21 13:28:38

def isPrime(n): #质数判断
for i in range(2,int(n/2)+1):
if n%i ==0:
return False
return True
def isDigital(n): #digital数判断
b=int(max(str(n)))
if sorted(str(n))==[str(i) for i in range(1,b+1)]:
return True
else:
return False
def main():
for n in [7,4]: #digital数位数n循环，2、3、5、6、8、9位digital数均能被3整除
x='' #获得最大的n位digital数
for i in range(n,0,-1):
x+=str(i)
num1=int(x)
y='' #获得最小的n位digital数
for i in range(1,n+1):
y+=str(i)
num2=int(y)
for i in range(num1,num2-1,-9): #digital数相差9的倍数
if isDigital(i)and isPrime(i):
print('找到了',i)
return
if __name__=='__main__':
main()

复制代码

方法比较笨，没想到更好的digital数排列组合方法。
结果是7652413

FDMa · 发表于 2016-10-23 22:05:38

本帖最后由 FDMa 于 2016-10-23 22:32 编辑

7652413，找到这么一个数，我也不知道是不是最大的
如果n=13，或者更大怎么算

electricity-py · 发表于 2016-11-14 21:29:18

jerryxjr1220 发表于 2016-10-17 11:05
这题其实有好多解法，我也想正好借这题，分享一些使用python解决一些数学题的心得。
【版主，在比赛结束后 ...

写的很好，思路简明清晰，看了这么多有关质数判断的帖子，这一篇写的最好

会抓贼的老托比 · 发表于 2016-11-15 08:33:03

非常棒，围观学习

shigure_takimi · 发表于 2018-3-1 14:10:13

from time import time
from itertools import permutations
def isPrime(n):
if n <= 1:
return False
elif n == 2 or n == 3:
return True
else:
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
else:
return True
t1 = time()
maxPandigital = 0
for i in range(9, 0, -1):
a = permutations('123456789'[:i], i)
for j in a:
number = int(''.join(j))
if isPrime(number) and number > maxPandigital:
maxPandigital = number
t2 = time()
print(maxPandigital)
print(t2 - t1)
## 7652413
## 1.65625

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20161017 最大的n位pandigital质数是多少？

马上注册，结交更多好友，享用更多功能^_^

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分