[已解决]python 最快速度找出范围内的素数

louisz90

0 < t ≤ 10&#8201;000               表示输入次数
0 < a ≤ 100&#8201;000                    
1 < n ≤ 1&#8201;000&#8201;000            a和n是另外需要输入的数字

打印所有素数 p （0 <=p<=10**7)
p满足 p=a*k+n （k是自然数）

如果没有这种素数，请打印“无”，不带引号。

最佳答案

月排行榜 / 总排行榜

久疤K

2018-5-5 22:46:59

1. for p in range(0,10**7+1):
   
2.     if p%n==a and prime(p):

复制代码

这是你的代码，而你需要满足的条件是

1. [color=Red]p=a*k+n[/color]

复制代码

显然代码应该改成

1. for p in range(0,10**7+1):
   
2.     if p%a==n and prime(p):

复制代码

这是我认为的错误，后优化代码为：

1. import sys  
   
2. import math  
   
3.   
   
4. def prime(n):  
   
5.     if n%2 == 0:  
   
6.         return n==2  
   
7.     if n%3 == 0:  
   
8.         return n==3  
   
9.     if n%5 == 0:  
   
10.         return n==5  
    
11.     for p in range(7,int(math.sqrt(n))+1,2):
    
12.         if n%p == 0:  
    
13.             return False  
    
14.     return True
    
15. 
    
16. 
    
17. t=int(input())
    
18. for i in range(t):
    
19.     Rien=True
    
20.     a,n=map(int,input().split())
    
21.     # for p in range(0,10**7+1):
    
22.     for p in range(n,10**7+1,a):
    
23.         # if p%n==a and prime(p):
    
24.         if prime(p):
    
25.             Rien=False
    
26.             print(p,end=" ")
    
27.     if Rien:
    
28.         print("None")
    
29.     print('\n')
    

复制代码

这样，效率提高 a 倍。
如此，为了达到显示的结果与你提供的结果一致，需要交换输入的两个数的位置。
如：

1. 3
   
2. 300000 1337
   
3. 12345 42
   
4. 100001 42

复制代码

另外，公式 p = a * k + n，可知，如果 a 和 n 有公约数，p 就不可能是素数，可以提高部分输入的效率，这点代码中未体现。

跳转到最佳答案楼层

louisz90

1. import sys  
   
2. import math  
   
3.   
   
4. def prime(n):  
   
5.     if n%2 == 0:  
   
6.         return n==2  
   
7.     if n%3 == 0:  
   
8.         return n==3  
   
9.     if n%5 == 0:  
   
10.         return n==5  
    
11.     for p in range(7,int(math.sqrt(n))+1,2):
    
12.         if n%p == 0:  
    
13.             return False  
    
14.     return True
    
15. 
    
16. 
    
17. t=int(input())
    
18. for i in range(t):
    
19.     Rien=True
    
20.     a,n=map(int,input().split())
    
21.     for p in range(0,10**7+1):
    
22.         if p%n==a and prime(p):
    
23.             Rien=False
    
24.             print(p,end=" ")
    
25.     if Rien:
    
26.         print("None")
    
27.     print('\n')
    

复制代码

我写的是对的 但是运行时间太长了，请问有什么方法优化一下？

久疤K

1. for p in range(0,10**7+1):
   
2.     if p%n==a and prime(p):

复制代码

这是你的代码，而你需要满足的条件是

1. [color=Red]p=a*k+n[/color]

复制代码

显然代码应该改成

1. for p in range(0,10**7+1):
   
2.     if p%a==n and prime(p):

复制代码

这是我认为的错误，后优化代码为：

1. import sys  
   
2. import math  
   
3.   
   
4. def prime(n):  
   
5.     if n%2 == 0:  
   
6.         return n==2  
   
7.     if n%3 == 0:  
   
8.         return n==3  
   
9.     if n%5 == 0:  
   
10.         return n==5  
    
11.     for p in range(7,int(math.sqrt(n))+1,2):
    
12.         if n%p == 0:  
    
13.             return False  
    
14.     return True
    
15. 
    
16. 
    
17. t=int(input())
    
18. for i in range(t):
    
19.     Rien=True
    
20.     a,n=map(int,input().split())
    
21.     # for p in range(0,10**7+1):
    
22.     for p in range(n,10**7+1,a):
    
23.         # if p%n==a and prime(p):
    
24.         if prime(p):
    
25.             Rien=False
    
26.             print(p,end=" ")
    
27.     if Rien:
    
28.         print("None")
    
29.     print('\n')
    

复制代码

这样，效率提高 a 倍。
如此，为了达到显示的结果与你提供的结果一致，需要交换输入的两个数的位置。
如：

1. 3
   
2. 300000 1337
   
3. 12345 42
   
4. 100001 42

复制代码

另外，公式 p = a * k + n，可知，如果 a 和 n 有公约数，p 就不可能是素数，可以提高部分输入的效率，这点代码中未体现。

louisz90

久疤K 发表于 2018-5-5 22:46
这是你的代码，而你需要满足的条件是
显然代码应该改成
这是我认为的错误，后优化代码为：

谢谢啦