小练习：20160919 找出所有11个可以双向裁剪的质数

冬雪雪冬 · 发表于 2016-9-19 11:04:30

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

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

x

本帖最后由冬雪雪冬于 2016-9-26 11:06 编辑

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

登录/注册后可看大图

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

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

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

题目：

3797 这个数很有趣。它本身是质数，而且如果我们从左边不断地裁去数字，得到的仍然都是质数：3797, 797, 97, 7。而且我们还可以从右向左裁剪：3797, 379, 37, 3，得到的仍然都是质数。

找出全部 11 个这样从左向右和从右向左都可以裁剪的质数。

注意：2, 3, 5 和 7 不被认为是可裁剪的质数。

tuotuoer · 发表于 2016-9-19 12:35:24

好棒

jerryxjr1220 · 发表于 2016-9-20 17:07:23

本帖最后由 jerryxjr1220 于 2016-9-25 05:05 编辑

这题思路从数的构成开始，若要满足条件，则：
1. 第1位必然由2，3，5，7组成
2.除第1及最后1位的中间数由1，3，7，9组成
3.最后1位由3，7组成
按照各种排列组合，然后筛选结果。
最后得到：23，37，73，53，313，373，317，797，3137，3797，739397正好11个数。
程序回去再贴。

def isPrime(num):
flag = 1
if num == 2 or num == 3:
return 1
elif num % 2 == 0:
return 0
else:
for i in range(3,int(num**0.5+1),2):
if num % i == 0:
flag = 0
break
return flag
def isCycle(strnum):
flags = 1
if isPrime(int(strnum)) == 0:
flags = 0
else:
length = len(strnum)
for l in range(length):
if isPrime(int(strnum[l:])) == 0 or isPrime(int(strnum[:l+1])) == 0:
flags = 0
break
return flags
lst1 = [2,3,5,7]
lst2 = [1,3,7,9]
lst3 = [3,7]
lst4 = [1,3,7,9]
lst = ['23','37','53','73']
final = []
for x in range(4):
for y in range(4):
lst4.append(lst2[x]*10+lst2[y])
for x in range(4):
for y in range(4):
for z in range(4):
lst4.append(lst2[x]*100+lst2[y]*10+lst2[z])
for x in range(4):
for y in range(4):
for z in range(4):
for w in range(4):
lst4.append(lst2[x]*1000+lst2[y]*100+lst2[z]*10+lst2[w])
for each in lst4:
for i in range(4):
for j in range(2):
lst.append(str(lst1[i])+str(each)+str(lst3[j]))
for eachi in lst:
if isCycle(eachi):
final.append (int(eachi))
final = set(final)
print (final)

复制代码

小剑剑 · 发表于 2016-9-21 16:33:04

from time import time
t=time()
def cut(number):
temp=10**(len(str(number))-1)
while temp>1:
yield number//temp
yield number%temp
temp//=10
yield 0
li=[0,0]+[1]*999999
primes=[]
for i in range(1000001):
if li[i]:
primes.append(i)
value=i*2
while(value<=1000000):
li[value]=0
value+=i
quantity=0
for i in primes[4:]:
if quantity>10:
break
iscut=True
cuts=cut(i)
while True:
cutnumber=next(cuts)
if cutnumber==0:
break
if cutnumber not in primes:
iscut=False
break
if iscut:
print(i)
quantity+=1
print(time()-t)

复制代码

最后一个太久了

23
37
53
73
313
317
373
797
3137
3797
739397
72.10999965667725

复制代码

老忘 · 发表于 2016-9-22 10:50:18

本帖最后由老忘于 2016-9-22 10:53 编辑

先说思路：一个n位的数字(根据要求知n>1),将其为为三段：首1位，中间n-2位，末1位，要满足左右截后都是质数
1、首1位只能是【2，3，5，7】。因为向左截到只有首位时要为质数
2、末位只能是【3，7】。因为向右截到只有末位时，可在【2，3，5，7】中选，但如果不截位时，末位【2，5】的不是质数，所以末位只能是【3，7】
3、中间n-2位只能是【1，3，7，9】。因为向左截时，中间任何一位数都可能变成末位，末位如果是偶数和5时，则不是质数。
4、将上述三段进行排列组合后，再进行截位质数判断。

# -*- coding:Utf-8 -*-
import itertools
import time,math
start = time.clock()
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
def check_all_zishu(ss): # 左右裁去数字进行质数判数
for i in range(0,len(ss)):
if isPrime(int(ss[0:i+1])):
if isPrime(int(ss[len(ss)-i-1:])):
pass
else:
return False
else:
return False
return True
list_start=[2,3,5,7] # 首位可能出现的数字
list_end=[3,7] # 末位可能出现的数字
# count记录左右截去后都为质数的数字的个数,m为除去首位和末位的中间部分的位数，并赋初值
count=0
m=0
while 1:
if count==11: # 如果找到11个，则跳出循环
break
else:
list_mid=[] # list_mid存放中间位数的列表
for eachone in list(itertools.product(['1','3','7','9'],repeat = m)): # 生成中间位数的列表
s=''
for each in eachone:
s+=each
list_mid.append(s)
# 通过list_start，list_mid,list_end来进行组合
for int_start in list_start:
for str_mid in list_mid:
for int_end in list_end:
aa=str(int_start)+str_mid+str(int_end)
if check_all_zishu(aa):
count+=1
print(aa)
m+=1
end = time.clock()
print ("read: %f s" % (end - start))

复制代码

计算结果：

23
37
53
73
313
317
373
797
3137
3797
739397
read: 0.025948 s

复制代码

飘飞的白杨 · 发表于 2016-9-24 09:16:19

本帖最后由飘飞的白杨于 2016-9-24 11:20 编辑

N = 1000000
l = int(N**0.5) + 1
prime = [False, False] + [True] * N
for i in range(2, l):
if prime[i]:
for j in range(2, N//i + 1):
if prime[j*i]:
prime[j*i] = False
m = 0
num = 0
def nnn(n):
x = [str(n),str(n)]
while len(x[0]) >= 1 and len(x[1]) >= 1:
if prime[int(x[0])] and prime[int(x[1])]:
x = [x[0][:-1],x[1][1:]]
else:
return False
global num,m
num += n
m += 1
n = 11
while True:
if m >= 11:
break
nnn(n)
n += 2
print(num)

复制代码

ps：我能吐槽题目要求中的时间错了吗？

bacon6581 · 发表于 2016-9-26 00:11:47

from time import time
start=time()
zs1=['2','3','7']
zs2=['2','3','5','7']
zs3=[2]
zs0=[]
zs=[]
def zhishu(a):
sq=a**0.5
if sq==int(sq):
return False
sq=int(sq)
for x in zs3:
if x>sq:
return True
if a/x==int(a/x):
return False
for i in range(3,1000000):
if zhishu(i):
zs3.append(i)
for i in zs3:
zs0.append(str(i))
for k in zs0:
if len(k)==2 and k[:1] in zs0 and k[-1:] in zs0:
zs.append(int(k))
elif len(k)==3 and k[:1] in zs0 and k[-1:] in zs0 and k[:2] in zs0 and k[-2:] in zs0:
zs.append(int(k))
elif len(k)==4 and k[:1] in zs0 and k[-1:] in zs0 and k[:2] in zs0 and k[-2:] in zs0 and k[:3] in zs0 and k[-3:] in zs0:
zs.append(int(k))
elif len(k)==5 and k[:1] in zs0 and k[-1:] in zs0 and k[:2] in zs0 and k[-2:] in zs0 and k[:3] in zs0 and k[-3:] in zs0 and k[:4] in zs0 and k[-4:] in zs0:
zs.append(int(k))
elif len(k)==6 and k[:1] in zs0 and k[-1:] in zs0 and k[:2] in zs0 and k[-2:] in zs0 and k[:3] in zs0 and k[-3:] in zs0 and k[:4] in zs0 and k[-4:] in zs0 and k[:5] in zs0 and k[-5:] in zs0:
zs.append(int(k))
print(zs)
print(time()-start)

复制代码

>>> ================================ RESTART ================================
>>>
[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
1369.6615242958069
>>>

复制代码

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

[技术交流] 小练习：20160919 找出所有11个可以双向裁剪的质数

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分