小练习：20170724 半质数

冬雪雪冬

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

                               
登录/注册后可看大图

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

----回帖需写明解题思路，鼓励在程序中加上注释


一些鱼油反映题目有些过难，为此略过一部分偏难的题目。



题目：

一个合数是至少两个质数因子的乘积，比如 15 = 3 × 5； 9 = 3 × 3； 12 = 2 × 2 × 3。

30 以内的数中有 10 个合数，它们有且仅有两个质数因子，这两个因子可能相同：4, 6, 9, 10, 14, 15, 21, 22, 25, 26。

请问，对于 n < 10⁸，有多少个数字只有两个质数因子？这两个质数因子可能相同

jerryxjr1220

这题暴力解法的逻辑还是比较容易写的，问题就是上限要达到10**8，所以运算速度就会成问题，好在有神器numpy和numba的jit，4秒就算出来了。
需要注意的是numba神器不支持列表推导式，也不支持python的列表添加和删除操作，所以如果有这些操作就需要把这些操作放在numba的jit装饰器之外。

1. import numpy as np
   
2. from numba import jit
   
3. @jit
   
4. def solve(n):
   
5.         sieve=np.ones(n+1,dtype=bool)
   
6.         for i in range(2, int((n+1)**0.5+1)):
   
7.                 if sieve[i]:
   
8.                         sieve[i*i::i]=False
   
9.         plist = np.nonzero(sieve)[0][2:]
   
10.         count = 0
    
11.         for i in range(len(plist)):
    
12.                 j = i
    
13.                 while plist[i]*plist[j] < n:
    
14.                         count += 1
    
15.                         j += 1
    
16.         return count
    
17. print(solve(10**8))

复制代码

17427258
[Finished in 4.5s]

plus

新手，刚好学到集合，尝试一下这道题

1. import time
   
2. tt = time.time()
   
3. 
   
4. m={}
   
5. for i in range(4,10000):
   
6.       
   
7.     a=[]
   
8.     b=[]
   
9.     for j in range(2,int(i/2)+1): #定义小于i的数j
   
10.             
    
11.         if i % j==0 :   #挨个除，能整除的就把被除数i和除数j存到a，b列表中
    
12.             a.append(i)
    
13.             b.append(j)
    
14.             if len(b)>2:break  #除数超过2个的舍弃
    
15.                
    
16.     if len(a)>2:i+=1  #被除数出现超过2次的舍弃
    
17.     elif len(b)<2 or b[1] not in m:m=set(m)|set(a) #除数唯一（比如4的除数只有2,9的除数只有3），或者第二个除数不在集合m中的（过滤掉8,27这样的），增加到集合m中
    
18. 
    
19. print(len(m))
    
20. print(time.time()-tt)
    
21. 
    

复制代码

解不出10^8这么大的。。
10^4 算出来是2625

达锅

难道有关质数的题目都要穷举吗？

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Tue Jul 25 21:56:15 2017
   
4. 
   
5. @author: 猛牛
   
6. """
   
7. 
   
8. '''一个合数是至少两个质数因子的乘积，比如 15 = 3 × 5； 9 = 3 × 3； 12 = 2 × 2 × 3。
   
9. 30 以内的数中有 10 个合数，它们有且仅有两个质数因子，这两个因子可能相同：4, 6, 9, 10, 14, 15, 21, 22, 25, 26。
   
10. 请问，对于 n < 10**8，有多少个数字只有两个质数因子？这两个质数因子可能相同'''
    
11. 
    
12. import time as t#直接就想到了求质素的筛法~
    
13. import numpy as np
    
14. #import itertools as ite
    
15. def js(i):
    
16.     if all[i]==0:
    
17.         all[i*2::i]=1
    
18.    
    
19.    
    
20. tt=t.time()
    
21. n=10**6
    
22. all=np.int64(np.zeros(n//2))#因为两个质数相乘，对于范围为n的数，最大可能质数范围为2×n/2，故找出到n//2的质数
    
23. all[:2]=1
    
24. all[4::2]=1
    
25. all[9::3]=1
    
26. 
    
27. for i in range(7,len(all)//2+1,6):#倍数赋值，取到一半即可
    
28.     js(i-2)
    
29.     js(i)
    
30. all=(np.where(all==0))[0]#数组下标就是质数
    
31. 
    
32. c=0
    
33. kf=(n**0.5)
    
34. 
    
35. for i in all:
    
36.    
    
37.     c+=len(np.where(all*i<=n)[0])-len(np.where(all<i)[0])#当n等于10**6时答案不对，原因不详……
    
38.     #c+=(len(np.where((all>=i)*(all*i<=n)==True)[0]))
    
39.     if i>kf:break#不加这一句用时翻倍
    
40. #==============================================================================
    
41. # for i in range(len(all)):
    
42. #     c+=len(np.where(all[i:]*all[i]<=n)[0])
    
43. #     if all[i]>kf:break
    
44. #==============================================================================
    
45. 
    
46. 
    
47. print(c)
    
48. 
    
49. print(t.time()-tt)

复制代码

suloman

先把 50000000以内所以质数 放入 数列a
然后每两个 质数相乘 不大于100000000的
只是不知道  数列 最多能放多少个数  会不会超出范围
a=[2,3]
b=10000
c=0
for i in range (5,int(b/2)):
   
    for j in range (2,int(i/2)+1):
        if i % j ==0:
            break
        if j== int(i/2):   
            a.append(i)
            
            

for i in range(0,len(a)):
    for j in range (i,len(a)):
        if a[i] * a[j] <b:
            #print(a[i]*a[j])
            c+=1
        else:
            break  
print (c)

张北京

           

小Q学Python

1.首先算出需要得到的所有质数：创建一个布尔数组，长度为最大数（为方便理解，多加一位，即index为1代表1），将0和1位置为False，从2开始，判断当前值是否为True，依次用2、3、5。。。将后面2的倍数、3的倍数、5的倍数位置的值置为False，遍历玩后，剩下True的即为质数
2.得到质数集后，可以找出其中的规律：譬如30以内的质数集为： 2  3  5 7 11 13    5的平方为25，再外后就超过临界值30，所以5前面的合数总数为（1+3）*3/2=6个（2*2 2*3 3*3 2*5 3*5 5*5）。往后，就需要验证：7需要往质数集前面找小质数，直到找到3，3的位置为第二位，所以7可以有2个（3*7 2*7）。后面的11直接根据上面的3的位置继续判断往前找，找到2，2的位置是第一位，所以为1个，以此类推

1. def zhishu_list(number):
   
2.     a = [True]*(number+1)
   
3.     a[0], a[1] = False, False
   
4.     for i in range(2,len(a)):
   
5.         if a[i] == True:
   
6.             for j in range(i+i,len(a),i):
   
7.                 a[j]=False
   
8.     b = [i for i,j in enumerate(a) if j==True]
   
9.     return b
   
10. 
    
11. max = 10**8
    
12. l = zhishu_list(int(max/2))     # 最小质数为2，所以只需找max值一半内的质数即可。
    
13. temp = int(max**0.5)
    
14. counts = 0
    
15. flag = 0
    
16. for i, j in enumerate(l):
    
17.     if flag == 0:
    
18.         if j > temp:
    
19.             counts = int((1+i)*i/2)
    
20.             flag = 1
    
21.             add_counts=i
    
22.     if flag == 1:
    
23.         for index in range(add_counts-1,-1,-1):
    
24.             if l[index]*j < max:
    
25.                 add_counts = index+1
    
26.                 counts += add_counts
    
27.                 break
    
28. 
    
29. print(counts)

复制代码

%time %run yuC_test3.py
17427258
Wall time: 26.7 s

plus

jerryxjr1220 发表于 2017-7-25 14:07
这题暴力解法的逻辑还是比较容易写的，问题就是上限要达到10**8，所以运算速度就会成问题，好在有神器numpy ...

真是大神，新手表示看不懂=。=

suloman

def zhishu_list(number):
    a = [True]*(number+1)
    a[0], a[1] = False, False
    for i in range(2,len(a)):
        if a[i] == True:
            for j in range(i+i,len(a),i):
                a[j]=False
    b = [i for i,j in enumerate(a) if j==True]
    return b
这个质数求法  服了

jerryxjr1220

suloman 发表于 2017-7-31 23:55
def zhishu_list(number):
    a = [True]*(number+1)
    a[0], a[1] = False, False

1. def zhishu_list(number):
   
2.         a = [True]*(number+1)
   
3.         a[0], a[1] = False, False
   
4.         for i in range(2,len(a)):
   
5.                 if a[i] == True:
   
6.                         for j in range(i+i,len(a),i):
   
7.                                 a[j]=False
   
8.         b = [i for i,j in enumerate(a) if j==True]
   
9.         return b

复制代码

for j in range(i+i,len(a),i) 这句的+号应该改为*号，结果是一样的，但是速度可以快很多。

用numpy写的话，就是这样：

1. sieve=np.ones(n+1,dtype=bool)
   
2. for i in range(2, int((n+1)**0.5+1)):
   
3.         if sieve[i]:
   
4.                 sieve[i*i::i]=False
   
5. plist = np.nonzero(sieve)[0][2:]

复制代码

suloman

jerryxjr1220 发表于 2017-8-1 08:22
for j in range(i+i,len(a),i) 这句的+号应该改为*号，结果是一样的，但是速度可以快很多。

用num ...

赞