小练习：20160905 100万以下有多少个循环质数

冬雪雪冬

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

                               
登录/注册后可看大图

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




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

----除列出程序外，请给出输出的结果。----


题目：

我们称 197 为一个循环质数，因为它的所有轮转形式： 197, 971 和 719 都是质数。

100 以下有 13 个这样的质数： 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和 97.

100 万以下有多少个循环质数？


-------------------------
我尝试了一下，用了几分钟才算出结果，准备重新写程序。看看大家有没有好的算法。

wangzhenas

基本思路是先用筛除法筛选出1，000，000以下质数，并转化为集合（为了快速验证元素是否为质数）
然后对集合内元素做迭代，对于每个元素按照该锁链法计算下一元素，若该元素不属于集合，则迭代下一元素
若属于则计算下一元素直到与开头元素重合即构成一条链

答案： 55
在我的机器上耗时：0.9s

from time import time

def primes_sieve(limit):
    limitn,not_prime,primes = limit+1,set(),list()
    for i in range(2, limitn):
        if i in not_prime:
            continue
        for f in range(i*2, limitn, i):
            not_prime.add(f)
        primes.append(i)
    return primes 
    
t = time()
i,d,prime_l = 0,1,primes_sieve(10**6)
prime_s = set(prime_l)

for item in prime_l:
    if 10*d < item:
        d *= 10   
    n_next,n_this = item//10 + (item%10)*d,item
    while n_next in prime_s:         
        n_next,n_this = n_this//10 + (n_this%10)*d,n_next
        if n_next == item:
            #print(n_next)
            i += 1
            break   
        
print(i,time()-t)
    

无下限HENTAI

import math
from time import time

start = time()
def is_prime(n):
    if n == 2 or n ==3:
        return True
    elif n%2 == 0:
        return False
    else:
        for i in range(3,int(math.sqrt(n))+1,2):
            if n%i == 0:
                return False
        return True
def next_prime(Max = 1000000):
    n = 3
    yield 2
    while n < Max:
        if is_prime(n):
            yield n
        n += 1
cir = [2,3,5,7]
for n in next_prime():
    if n in cir:
        continue
    else:
        n_str = str(n)
        maybe = [n]
        l = len(n_str)
        flag = 1
        for i in range(l-1):
            n_new_str = ''.join([n_str[-1],n_str[:-1]])
            n_new = int(n_new_str)
            n_str = n_new_str
            if is_prime(n_new):
                maybe.append(n_new)
            else:
                flag = 0
                break
        if flag == 1:
            for each in maybe:
                cir.append(each)
cir_set = set(cir)
cir = sorted(list(cir_set))
print('循环质数有：')
for each in cir:
    print(each,end = ' ')
print('\n共有%d个'%len(cir))
print('用时%.5fs'%(time()-start))

结果：
循环质数有：
2 3 5 7 11 13 17 31 37 71 73 79 97 113 131 197 199 311 337 373 719 733 919 971 991 1193 1931 3119 3779 7793 7937 9311 9377 11939 19391 19937 37199 39119 71993 91193 93719 93911 99371 193939 199933 319993 331999 391939 393919 919393 933199 939193 939391 993319 999331
共有55个
用时15.24187s

老忘

先说说思路吧！
只有1、3、7、9这四个数字组成的1-6位数的组合数，才有可能是循环质数（因为0、2、4、5、6、8排在最末一位，如果不是1位数，就肯定不是质数）
所以用这四个数来进行组合，再循环后判断是否全部为质数。

# -*- 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_nm(j): #是否为循环质数
    list_each=[]
    for each_str in j:
        list_each.append(each_str)
    for i in range(0,len(list_each)):
        s=''
        for each in list_each:
            s+=each
        if isPrime(int(s)):
            list_each.append(list_each[0])
            del list_each[0]
        else:
            return 0
    return 1

list_temp=['2','5']
for i in range(1, 7):
    for eachone in list(itertools.product(['1','3','7','9'],repeat = i)):
        s=''
        for aa in eachone:
            s+=aa
        if check_nm(s):
            list_temp.append(s)

print(len(list_temp))

end = time.clock()
print ("read: %f s" % (end - start))

结果：

55
read: 0.143897 s

lizuolong

import time
start=time.time()
def euler35(limit):
    def isprimesieve(n):
        sieve = bytearray([1])*(n+1)
        sieve[0] = sieve[1] = 0
        for p in range(2, int(n**0.5) + 1):
            if sieve[p]:
                m = n//p - p + 1
                sieve[p*p::p] = bytearray(m)
        return sieve

    def rotations(s):
        for n in range(len(s)): yield s[n:] + s[:n]

    count = 0; isprime = isprimesieve(limit); unwanted = '024568'
    for n, prime in enumerate(isprime):
        if prime:
            s = str(n)
            if any(c in s for c in unwanted): continue
            if all(isprime[int(r)] for r in rotations(s)):
                count += 1
    return count + 2
print(euler35(1000000),time.time()-start)

百度网络来的
55个，用时0.15s

hvagab

不知道对不对 如果错了 请指出 好改正过来

import time
start=time.clock()
def pr(n):#定义质数
    if n==2:return True
    if n<2:return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    else:
        return True

def xh(n):#定义循环数（例如123的循环数[231 312]  2538循环数[5382,3825 8253]
    l=[]
    lis1=list(str(n))#整数转换为列表
    for j in lis1:
        l.append(j)#整数转换为位数
    l1=l+l#发现加上一个后就可以直接循环例如123变成123123 循环体就在这个数上取数
    s=len(l)#得到这个l的长度  也就是这个整数的位数
    n=[]
    for i in range(s):
        m=''#定义空字符串
        l2 = l1[i:i+s]#从l1取位数跟n的位数相同的列表（也就是l长度的列表） 因为l1的位数是l的2倍
        for k  in l2:
            m=m+k
        num=int(m)
        n.append(num)
    return n

count=13
for x in range(100,1000000):
    y=xh(x)
    ma=map(pr,y)
    if False not in ma:
        count+=1
        print(y)
print(count)
print(time.clock()-start)

hvagab

输出结果55

小剑剑

from time import time
quantity,raw_num,primenum,begin=0,[1]*(10**6+1),[],time()
for i in range(2,10**6+1):
       if raw_num[i]:
              primenum.append(i)
              value=i
              while value<=10**6:
                     raw_num[value]=0
                     value+=i

primenum.append(10**5)
primenum=sorted(primenum)
smallnum=primenum[:primenum.index(10**5)]
largenum=primenum[primenum.index(10**5):]
def circlenum(num):
       li=list(str(num))
       cirnum=set()
       for i in range(1,len(str(num))):
              cirnum.add(int(''.join(li[i:]+li[:i])))
       return tuple(cirnum)
for i in smallnum:
       nums=circlenum(i)
       if_cirnu=True
       for ii in nums:
              if ii not in smallnum:
                     if_cirnu=False
                     break
       if if_cirnu:
              quantity+=1
              
for i in largenum:
       nums=circlenum(i)
       if_cirnu=True
       for ii in nums:
              if ii not in largenum:
                     if_cirnu=False
                     break
       if if_cirnu:
              quantity+=1
print(time()-begin,quantity)

55

又改进了一下

from time import time
quantity,raw_num,primenum,begin,even=0,[1]*(10**6+1),[],time(),set('02468')
for i in range(2,10**6+1):
       if raw_num[i]:
              primenum.append(i)
              value=i
              while value<=10**6:
                     raw_num[value]=0
                     value+=i
for i in primenum:#这里把2去掉了
       if set(str(i))&even:
              primenum.remove(i)
primenum.append(2)#把2补上
primenum.append(10**5)
primenum=sorted(primenum)
smallnum=primenum[:primenum.index(10**5)]
largenum=primenum[primenum.index(10**5)-1:]
def circlenum(num):
       li=list(str(num))
       cirnum=set()
       for i in range(1,len(str(num))):
              cirnum.add(int(''.join(li[i:]+li[:i])))
       return tuple(cirnum)
for i in smallnum:
       nums=circlenum(i)
       if_cirnu=True
       for ii in nums:
              if ii not in smallnum:
                     if_cirnu=False
                     break
       if if_cirnu:
              quantity+=1

              
for i in largenum:
       nums=circlenum(i)
       if_cirnu=True
       for ii in nums:
              if ii not in largenum:
                     if_cirnu=False
                     break
       if if_cirnu:
              quantity+=1
print(time()-begin,quantity)

天外飞mao

看看~~~

mather

import time
on= time.time()

import math
import itertools

def is_primes(num):
    res = True
    for j in range(3,int(math.sqrt(num)+1),2):
        if num%j==0:
            return False
    return res
ressets = set([2,3,5,7])
for i in range(11,1000000):
    if i in ressets:
        continue
    tem = []
    tem_i = i
    is_break = False
    while tem_i>0:
        gewei = tem_i%10
        if gewei%2==0:
            is_break = True
            break
        else:
            tem.append(gewei)
            tem_i = tem_i//10
    if is_break:
        continue
    else:
        tem.reverse()
        weishu = len(tem)
        for j in range(weishu-1):#扩展tem列表，如[1,9,7,1,9]
            tem.append(tem[j])
        sets = set()
        for j in range(weishu):
            tem_pri = 0
            for ii in range(j,j+weishu):#生成所有循环数
                tem_pri = tem_pri*10+tem[ii]
            sets.add(tem_pri)
        type = 0
        for o in sets:
            if o in ressets or not is_primes(o):
                type = 1
                break
        if type != 0:
            continue
        else:
            ressets = ressets.union(sets)
print(len(ressets))
print(time.time()-on)

计算结果：55
耗时：1.22s

loserlovey

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 07 21:24:54 2016

@author: sychen
"""

def gen_primes(): 
    yield 2 
    yield 3 
    i = 5 
    while True: 
        if is_prime(i): 
            yield i 
        i += 2 
        
def is_prime(n): 
    if n <= 1: 
        return False 
    elif n == 2: 
        return True 
    elif n % 2 == 0: 
        return False 
    else: 
        d = 3 
        while d * d <= n: 
            if n % d == 0: 
                return False 
            d += 2 
        return True
        
        
def is_loop_prime(n): 
    length = len(str(n))
    temp = n
    for i in range(1, length+1):
        if not is_prime(temp):
            return False
        temp = temp / 10 + (temp % 10) * (10 ** (length-1))
    return True
    
        
def fishc20160905(limit):
    gen = gen_primes()
    count = 0
    test = gen.next()
    while  test < limit:
        if is_loop_prime(test):
            count += 1
        test = gen.next()
    return count

   
        
fishc20160905(100)
55

%timeit fishc20160905(1000000)
1 loop, best of 3: 7.32 s per loop

过河的小卒

import math

def judgePrime(num):
    if num%2 == 0:
        return False
    for i in range(3,int(math.sqrt(num))+1,2):
        if not num%i:
            return False
    else:
        return True

numList = [2,3,5,7]
for num in range(11,1000000):
    for s in str(num):
        if s in ['2','4','6','8','0','5']:
            break
    else:
        if judgePrime(num):
            flag = 0
            s = str(num)[1:] + str(num)[:1]
            while s != str(num):
                if not judgePrime(int(s)):
                    flag = 1
                    break
                s = s[1:] + s[:1]
            if flag == 0:
                numList.append(num)

print(len(numList))

结果为55

sunqiangzai

#python 3.5.1
import math

def is_prime(n, dict_primes):
    if n in dict_primes:
        return dict_primes[n]

    for num in range(2, math.floor(math.sqrt(n)+1)):
        if n % num == 0:
            dict_primes[n] = False
            return False
    dict_primes[n] = True
    return True


def main():
    """Main function"""
    count = 0
    dict_primes = {}

    for num in range (2, 1000000):
        q = False
        num = str(num)
        for i in range(len(num)):
            if is_prime(int(num[i:]+num[:i]), dict_primes):
                q = True
            else:
                q = False
                break
        if q:
            count += 1
    print (count)

if __name__ == "__main__":
    main()

C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\python.exe H:/python-code/欧拉35.py
55

Process finished with exit code 0

bacon6581

from time import time
start=time()
result=set()
zhishu=[2,3,5,7]
zhishu_str=[]
for i in range(10,1000):
    sq=i**0.5
    if sq==int(sq):
        next
    sq=int(sq)

    pd=True
    for j in zhishu:
        if i/j==int(i/j):
            pd=False
            break
        if j>=sq:
            break

    if pd==True:
        zhishu.append(i)

for i in  range(1001,1000000):
    j=str(i)
    if ('5' not in j) and ('0' not in j) and ('2' not in j) and ('4' not in j) and ('6' not in j) and ('8' not in j):
        sq=i**0.5
        if sq==int(sq):
            next
        sq=int(sq)

        pd=True
        for j in zhishu:
            if i/j==int(i/j):
                pd=False
                break
            if j>=sq:
                break

        if pd==True:
            zhishu_str.append(str(i))

for i in zhishu:
    if i>1000:
        break
    j=str(i)
    if ('5' not in j) and ('0' not in j) and ('2' not in j) and ('4' not in j) and ('6' not in j) and ('8' not in j):
        zhishu_str.append(str(i))
zhishu_str.append('5')
zhishu_str.append('2')
#print(time()-start)

while len(zhishu_str)>0:
    if len(zhishu_str[0])<2:
        result.add(zhishu_str[0])
        zhishu_str.remove(zhishu_str[0])
    else:
        k=zhishu_str[0]
        n=1
        zs=True
        while n<len(k):
            n+=1
            k=k[1:]+k[0]
            if k not in zhishu_str:
                zs=False
                zhishu_str.remove(zhishu_str[0])
                break
        if zs==True:
            k=zhishu_str[0]
            result.add(zhishu_str[0])
            zhishu_str.remove(zhishu_str[0])
            n=1
            while n<len(k):
                n+=1
                k=k[1:]+k[0]
                if k in zhishu_str:
                    result.add(k)
                    zhishu_str.remove(k)
                
#print(result)
print(len(result))
print(time()-start)

>>> ================================ RESTART ================================
>>> 
{'993319', '373', '193939', '939391', '939193', '1193', '1931', '13', '197', '2', '37199', '19937', '319993', '91193', '31', '71', '9377', '39119', '5', '391939', '11939', '17', '3119', '3', '991', '71993', '93911', '199', '73', '337', '3779', '393919', '719', '11', '919393', '933199', '7937', '311', '331999', '79', '7', '93719', '7793', '999331', '19391', '9311', '99371', '37', '971', '919', '199933', '113', '131', '97', '733'}
55
7.932184457778931

一不小心，杀到了10秒内。介绍下思路：

第一种方法（需半小时）：
1、求出1000000以内的所有质数并存放在列表中。
2、判断其中一个数的所有轮转形式是否都在列表中，是的话把这个数及轮转形式都放入集合中。
3、统计集合里元素有多少。

第二种方法（需两分钟）：
1、求出1000000以内的所有质数并存放在列表中。
2、如列表中的元素含有0、2、3、4、5、6、8的，直接删掉（2、5）除外。因为他们的轮转中这几个值必然有机会跑到个位，这时就能被2或5整除。（如23轮转到32 , 53轮转到35）
3、再判断新列表中一个数的所有轮转形式是否都在列表中，是的话把这个数及轮转形式都放入集合中。
4、统计集合里元素有多少。

第三种方法（10秒内）：
1、求出1000以内的所有质数并存放在列表中（一百万的平方根就是1000）。主要用来判断100万 以内的数是否为质数
2、再求1001-100万之间的一些特殊的质数（如果这个数含有0、2、3、4、5、6、8的，直接Pass掉，用不着判断质数了，原因见方法二的第2点）。
3、剔除10-1000之间其中任意一位含有0、2、3、4、5、6、8的质数。
4、再判断新列表中一个数的所有轮转形式是否都在列表中，是的话把这个数及轮转形式都放入集合中。
5、统计集合里元素有多少。