小练习：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个可以双向裁剪的质数

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分