小练习：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

1. from time import time
   
2. 
   
3. def primes_sieve(limit):
   
4.     limitn,not_prime,primes = limit+1,set(),list()
   
5.     for i in range(2, limitn):
   
6.         if i in not_prime:
   
7.             continue
   
8.         for f in range(i*2, limitn, i):
   
9.             not_prime.add(f)
   
10.         primes.append(i)
    
11.     return primes
    
12.    
    
13. t = time()
    
14. i,d,prime_l = 0,1,primes_sieve(10**6)
    
15. prime_s = set(prime_l)
    
16. 
    
17. for item in prime_l:
    
18.     if 10*d < item:
    
19.         d *= 10   
    
20.     n_next,n_this = item//10 + (item%10)*d,item
    
21.     while n_next in prime_s:         
    
22.         n_next,n_this = n_this//10 + (n_this%10)*d,n_next
    
23.         if n_next == item:
    
24.             #print(n_next)
    
25.             i += 1
    
26.             break   
    
27.         
    
28. print(i,time()-t)
    
29.    

复制代码

无下限HENTAI

1. import math
   
2. from time import time
   
3. 
   
4. start = time()
   
5. def is_prime(n):
   
6.     if n == 2 or n ==3:
   
7.         return True
   
8.     elif n%2 == 0:
   
9.         return False
   
10.     else:
    
11.         for i in range(3,int(math.sqrt(n))+1,2):
    
12.             if n%i == 0:
    
13.                 return False
    
14.         return True
    
15. def next_prime(Max = 1000000):
    
16.     n = 3
    
17.     yield 2
    
18.     while n < Max:
    
19.         if is_prime(n):
    
20.             yield n
    
21.         n += 1
    
22. cir = [2,3,5,7]
    
23. for n in next_prime():
    
24.     if n in cir:
    
25.         continue
    
26.     else:
    
27.         n_str = str(n)
    
28.         maybe = [n]
    
29.         l = len(n_str)
    
30.         flag = 1
    
31.         for i in range(l-1):
    
32.             n_new_str = ''.join([n_str[-1],n_str[:-1]])
    
33.             n_new = int(n_new_str)
    
34.             n_str = n_new_str
    
35.             if is_prime(n_new):
    
36.                 maybe.append(n_new)
    
37.             else:
    
38.                 flag = 0
    
39.                 break
    
40.         if flag == 1:
    
41.             for each in maybe:
    
42.                 cir.append(each)
    
43. cir_set = set(cir)
    
44. cir = sorted(list(cir_set))
    
45. print('循环质数有：')
    
46. for each in cir:
    
47.     print(each,end = ' ')
    
48. print('\n共有%d个'%len(cir))
    
49. 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位数，就肯定不是质数）
所以用这四个数来进行组合，再循环后判断是否全部为质数。

1. # -*- coding:Utf-8 -*-
   
2. import itertools
   
3. import time,math
   
4. start = time.clock()
   
5. 
   
6. def isPrime(n):#质数判断
   
7.     if n == 1:
   
8.         return False
   
9.     elif n < 4:
   
10.         return True
    
11.     elif n & 1 == 0:
    
12.         return False
    
13.     elif n < 9:
    
14.         return True
    
15.     elif n %3 == 0:
    
16.         return False
    
17.     else:
    
18.         r = math.floor(math.sqrt(n))
    
19.         f = 5
    
20.         while f <= r:
    
21.             if n % f == 0:
    
22.                 return False
    
23.             if n %(f+2) == 0:
    
24.                 return False
    
25.             f += 6
    
26.         return True
    
27. 
    
28. def check_nm(j): #是否为循环质数
    
29.     list_each=[]
    
30.     for each_str in j:
    
31.         list_each.append(each_str)
    
32.     for i in range(0,len(list_each)):
    
33.         s=''
    
34.         for each in list_each:
    
35.             s+=each
    
36.         if isPrime(int(s)):
    
37.             list_each.append(list_each[0])
    
38.             del list_each[0]
    
39.         else:
    
40.             return 0
    
41.     return 1
    
42. 
    
43. list_temp=['2','5']
    
44. for i in range(1, 7):
    
45.     for eachone in list(itertools.product(['1','3','7','9'],repeat = i)):
    
46.         s=''
    
47.         for aa in eachone:
    
48.             s+=aa
    
49.         if check_nm(s):
    
50.             list_temp.append(s)
    
51. 
    
52. print(len(list_temp))
    
53. 
    
54. end = time.clock()
    
55. print ("read: %f s" % (end - start))

复制代码

结果：

1. 55
   
2. read: 0.143897 s

复制代码

lizuolong

1. import time
   
2. start=time.time()
   
3. def euler35(limit):
   
4.     def isprimesieve(n):
   
5.         sieve = bytearray([1])*(n+1)
   
6.         sieve[0] = sieve[1] = 0
   
7.         for p in range(2, int(n**0.5) + 1):
   
8.             if sieve[p]:
   
9.                 m = n//p - p + 1
   
10.                 sieve[p*p::p] = bytearray(m)
    
11.         return sieve
    
12. 
    
13.     def rotations(s):
    
14.         for n in range(len(s)): yield s[n:] + s[:n]
    
15. 
    
16.     count = 0; isprime = isprimesieve(limit); unwanted = '024568'
    
17.     for n, prime in enumerate(isprime):
    
18.         if prime:
    
19.             s = str(n)
    
20.             if any(c in s for c in unwanted): continue
    
21.             if all(isprime[int(r)] for r in rotations(s)):
    
22.                 count += 1
    
23.     return count + 2
    
24. 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

小剑剑

1. from time import time
   
2. quantity,raw_num,primenum,begin=0,[1]*(10**6+1),[],time()
   
3. for i in range(2,10**6+1):
   
4.        if raw_num[i]:
   
5.               primenum.append(i)
   
6.               value=i
   
7.               while value<=10**6:
   
8.                      raw_num[value]=0
   
9.                      value+=i
   
10. 
    
11. primenum.append(10**5)
    
12. primenum=sorted(primenum)
    
13. smallnum=primenum[:primenum.index(10**5)]
    
14. largenum=primenum[primenum.index(10**5):]
    
15. def circlenum(num):
    
16.        li=list(str(num))
    
17.        cirnum=set()
    
18.        for i in range(1,len(str(num))):
    
19.               cirnum.add(int(''.join(li[i:]+li[:i])))
    
20.        return tuple(cirnum)
    
21. for i in smallnum:
    
22.        nums=circlenum(i)
    
23.        if_cirnu=True
    
24.        for ii in nums:
    
25.               if ii not in smallnum:
    
26.                      if_cirnu=False
    
27.                      break
    
28.        if if_cirnu:
    
29.               quantity+=1
    
30.               
    
31. for i in largenum:
    
32.        nums=circlenum(i)
    
33.        if_cirnu=True
    
34.        for ii in nums:
    
35.               if ii not in largenum:
    
36.                      if_cirnu=False
    
37.                      break
    
38.        if if_cirnu:
    
39.               quantity+=1
    
40. print(time()-begin,quantity)
    
41. 
    
42. 55

复制代码

又改进了一下

1. from time import time
   
2. quantity,raw_num,primenum,begin,even=0,[1]*(10**6+1),[],time(),set('02468')
   
3. for i in range(2,10**6+1):
   
4.        if raw_num[i]:
   
5.               primenum.append(i)
   
6.               value=i
   
7.               while value<=10**6:
   
8.                      raw_num[value]=0
   
9.                      value+=i
   
10. for i in primenum:#这里把2去掉了
    
11.        if set(str(i))&even:
    
12.               primenum.remove(i)
    
13. primenum.append(2)#把2补上
    
14. primenum.append(10**5)
    
15. primenum=sorted(primenum)
    
16. smallnum=primenum[:primenum.index(10**5)]
    
17. largenum=primenum[primenum.index(10**5)-1:]
    
18. def circlenum(num):
    
19.        li=list(str(num))
    
20.        cirnum=set()
    
21.        for i in range(1,len(str(num))):
    
22.               cirnum.add(int(''.join(li[i:]+li[:i])))
    
23.        return tuple(cirnum)
    
24. for i in smallnum:
    
25.        nums=circlenum(i)
    
26.        if_cirnu=True
    
27.        for ii in nums:
    
28.               if ii not in smallnum:
    
29.                      if_cirnu=False
    
30.                      break
    
31.        if if_cirnu:
    
32.               quantity+=1
    
33. 
    
34.               
    
35. for i in largenum:
    
36.        nums=circlenum(i)
    
37.        if_cirnu=True
    
38.        for ii in nums:
    
39.               if ii not in largenum:
    
40.                      if_cirnu=False
    
41.                      break
    
42.        if if_cirnu:
    
43.               quantity+=1
    
44. print(time()-begin,quantity)

复制代码

天外飞mao

看看~~~

mather

1. import time
   
2. on= time.time()
   
3. 
   
4. import math
   
5. import itertools
   
6. 
   
7. def is_primes(num):
   
8.     res = True
   
9.     for j in range(3,int(math.sqrt(num)+1),2):
   
10.         if num%j==0:
    
11.             return False
    
12.     return res
    
13. ressets = set([2,3,5,7])
    
14. for i in range(11,1000000):
    
15.     if i in ressets:
    
16.         continue
    
17.     tem = []
    
18.     tem_i = i
    
19.     is_break = False
    
20.     while tem_i>0:
    
21.         gewei = tem_i%10
    
22.         if gewei%2==0:
    
23.             is_break = True
    
24.             break
    
25.         else:
    
26.             tem.append(gewei)
    
27.             tem_i = tem_i//10
    
28.     if is_break:
    
29.         continue
    
30.     else:
    
31.         tem.reverse()
    
32.         weishu = len(tem)
    
33.         for j in range(weishu-1):#扩展tem列表，如[1,9,7,1,9]
    
34.             tem.append(tem[j])
    
35.         sets = set()
    
36.         for j in range(weishu):
    
37.             tem_pri = 0
    
38.             for ii in range(j,j+weishu):#生成所有循环数
    
39.                 tem_pri = tem_pri*10+tem[ii]
    
40.             sets.add(tem_pri)
    
41.         type = 0
    
42.         for o in sets:
    
43.             if o in ressets or not is_primes(o):
    
44.                 type = 1
    
45.                 break
    
46.         if type != 0:
    
47.             continue
    
48.         else:
    
49.             ressets = ressets.union(sets)
    
50. print(len(ressets))
    
51. print(time.time()-on)

复制代码

计算结果：55
耗时：1.22s

loserlovey

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Wed Sep 07 21:24:54 2016
   
4. 
   
5. @author: sychen
   
6. """
   
7. 
   
8. def gen_primes():
   
9.     yield 2
   
10.     yield 3
    
11.     i = 5
    
12.     while True:
    
13.         if is_prime(i):
    
14.             yield i
    
15.         i += 2
    
16.         
    
17. def is_prime(n):
    
18.     if n <= 1:
    
19.         return False
    
20.     elif n == 2:
    
21.         return True
    
22.     elif n % 2 == 0:
    
23.         return False
    
24.     else:
    
25.         d = 3
    
26.         while d * d <= n:
    
27.             if n % d == 0:
    
28.                 return False
    
29.             d += 2
    
30.         return True
    
31.         
    
32.         
    
33. def is_loop_prime(n):
    
34.     length = len(str(n))
    
35.     temp = n
    
36.     for i in range(1, length+1):
    
37.         if not is_prime(temp):
    
38.             return False
    
39.         temp = temp / 10 + (temp % 10) * (10 ** (length-1))
    
40.     return True
    
41.    
    
42.         
    
43. def fishc20160905(limit):
    
44.     gen = gen_primes()
    
45.     count = 0
    
46.     test = gen.next()
    
47.     while  test < limit:
    
48.         if is_loop_prime(test):
    
49.             count += 1
    
50.         test = gen.next()
    
51.     return count

复制代码

   
        
fishc20160905(100)
55

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

过河的小卒

1. import math
   
2. 
   
3. def judgePrime(num):
   
4.     if num%2 == 0:
   
5.         return False
   
6.     for i in range(3,int(math.sqrt(num))+1,2):
   
7.         if not num%i:
   
8.             return False
   
9.     else:
   
10.         return True
    
11. 
    
12. numList = [2,3,5,7]
    
13. for num in range(11,1000000):
    
14.     for s in str(num):
    
15.         if s in ['2','4','6','8','0','5']:
    
16.             break
    
17.     else:
    
18.         if judgePrime(num):
    
19.             flag = 0
    
20.             s = str(num)[1:] + str(num)[:1]
    
21.             while s != str(num):
    
22.                 if not judgePrime(int(s)):
    
23.                     flag = 1
    
24.                     break
    
25.                 s = s[1:] + s[:1]
    
26.             if flag == 0:
    
27.                 numList.append(num)
    
28. 
    
29. print(len(numList))

复制代码

结果为55

sunqiangzai

1. #python 3.5.1
   
2. import math
   
3. 
   
4. def is_prime(n, dict_primes):
   
5.     if n in dict_primes:
   
6.         return dict_primes[n]
   
7. 
   
8.     for num in range(2, math.floor(math.sqrt(n)+1)):
   
9.         if n % num == 0:
   
10.             dict_primes[n] = False
    
11.             return False
    
12.     dict_primes[n] = True
    
13.     return True
    
14. 
    
15. 
    
16. def main():
    
17.     """Main function"""
    
18.     count = 0
    
19.     dict_primes = {}
    
20. 
    
21.     for num in range (2, 1000000):
    
22.         q = False
    
23.         num = str(num)
    
24.         for i in range(len(num)):
    
25.             if is_prime(int(num[i:]+num[:i]), dict_primes):
    
26.                 q = True
    
27.             else:
    
28.                 q = False
    
29.                 break
    
30.         if q:
    
31.             count += 1
    
32.     print (count)
    
33. 
    
34. if __name__ == "__main__":
    
35.     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

1. from time import time
   
2. start=time()
   
3. result=set()
   
4. zhishu=[2,3,5,7]
   
5. zhishu_str=[]
   
6. for i in range(10,1000):
   
7.     sq=i**0.5
   
8.     if sq==int(sq):
   
9.         next
   
10.     sq=int(sq)
    
11. 
    
12.     pd=True
    
13.     for j in zhishu:
    
14.         if i/j==int(i/j):
    
15.             pd=False
    
16.             break
    
17.         if j>=sq:
    
18.             break
    
19. 
    
20.     if pd==True:
    
21.         zhishu.append(i)
    
22. 
    
23. for i in  range(1001,1000000):
    
24.     j=str(i)
    
25.     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):
    
26.         sq=i**0.5
    
27.         if sq==int(sq):
    
28.             next
    
29.         sq=int(sq)
    
30. 
    
31.         pd=True
    
32.         for j in zhishu:
    
33.             if i/j==int(i/j):
    
34.                 pd=False
    
35.                 break
    
36.             if j>=sq:
    
37.                 break
    
38. 
    
39.         if pd==True:
    
40.             zhishu_str.append(str(i))
    
41. 
    
42. for i in zhishu:
    
43.     if i>1000:
    
44.         break
    
45.     j=str(i)
    
46.     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):
    
47.         zhishu_str.append(str(i))
    
48. zhishu_str.append('5')
    
49. zhishu_str.append('2')
    
50. #print(time()-start)
    
51. 
    
52. while len(zhishu_str)>0:
    
53.     if len(zhishu_str[0])<2:
    
54.         result.add(zhishu_str[0])
    
55.         zhishu_str.remove(zhishu_str[0])
    
56.     else:
    
57.         k=zhishu_str[0]
    
58.         n=1
    
59.         zs=True
    
60.         while n<len(k):
    
61.             n+=1
    
62.             k=k[1:]+k[0]
    
63.             if k not in zhishu_str:
    
64.                 zs=False
    
65.                 zhishu_str.remove(zhishu_str[0])
    
66.                 break
    
67.         if zs==True:
    
68.             k=zhishu_str[0]
    
69.             result.add(zhishu_str[0])
    
70.             zhishu_str.remove(zhishu_str[0])
    
71.             n=1
    
72.             while n<len(k):
    
73.                 n+=1
    
74.                 k=k[1:]+k[0]
    
75.                 if k in zhishu_str:
    
76.                     result.add(k)
    
77.                     zhishu_str.remove(k)
    
78.                
    
79. #print(result)
    
80. print(len(result))
    
81. print(time()-start)
    

复制代码

1. >>> ================================ RESTART ================================
   
2. >>>
   
3. {'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'}
   
4. 55
   
5. 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、统计集合里元素有多少。