[已解决]求大佬帮忙 质数问题

Tac

为标准输入（stdin）的每一行给定一个正整数，需要输出不超过该整数的质数个数。当输入文本为空行时，程序必须完成。
要求：可以使用Eratosthenes’s筛算法，另外该问题中对计算速度要求较高，这意味着代码应该尽可能快地回答更大的数字情况。
也就是说代码需要能在可接受的时间内正确地回答像100000或10000000这样的大数的情况。
请将编码的主要思路记录在备注中。
下图为输入输出示例

                               
登录/注册后可看大图

最佳答案

月排行榜 / 总排行榜

逃兵

2020-12-19 16:53:03

1. def get_primes(n: int) -> list:
   
2.     """
   
3.     return a list containing all prime numbers less than n.
   
4.     """
   
5.     if n <= 2:
   
6.         return []
   
7.     isprime = [True for _ in range(n)]
   
8.     result = [2]
   
9.     for i in range(3, n, 2):
   
10.         if isprime[i]:
    
11.             result.append(i)
    
12.         for j in range(0, len(result)):
    
13.             if i * result[j] >= n:
    
14.                 break
    
15.             isprime[i * result[j]] = False
    
16.             if i % result[j] == 0:
    
17.                 break
    
18.     return len(result)
    
19. 
    
20. lst=[]
    
21. n=input()
    
22. while n:
    
23.     n=int(n)
    
24.     lst.append(n)
    
25.     n=input()
    
26. for n in lst:
    
27.     print(get_primes(n))
    

复制代码

跳转到最佳答案楼层

逃兵

1. import math
   
2. def func_get_prime(n):
   
3.   return len(list(filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i ==0], range(2,n+1))))
   
4. lst=[]
   
5. n=input()
   
6. while n:
   
7.     n=int(n)
   
8.     lst.append(n)
   
9.     n=input()
   
10. for n in lst:
    
11.     print(func_get_prime(n))

复制代码

Tac

逃兵 发表于 2020-12-19 14:59

输入为10000000时没有输出什么情况啊

逃兵

1. 1000
   
2. 100000
   
3. 10000000
   
4. 
   
5. 168
   
6. 9592
   
7. 664579
   
8. >>>

复制代码

计算量大，运行时间长，一直等着就出来了
可接受的时间内，这个概念比较模糊，实际上需要的时间挺长的

Tac

逃兵 发表于 2020-12-19 15:36
计算量大，运行时间长，一直等着就出来了
可接受的时间内，这个概念比较模糊，实际上需要的时间挺长的

那可以通过编程缩短这个时间吗？要求是输入越大计算时间要尽可能短。

逃兵

1. def func_get_prime(n):
   
2.     count = 3
   
3.     primenumbers = [3,5]
   
4.     x = 7
   
5.     step = 4
   
6.     while x < n:
   
7.         flag = False
   
8.         j = int(x ** 0.5)
   
9.         if x % 5 != 0:
   
10.             for i in primenumbers:
    
11.                 if i > j:
    
12.                     flag = True
    
13.                     break
    
14.                 if x % i == 0:
    
15.                     flag = False
    
16.                     break
    
17.             if flag:
    
18.                 count += 1
    
19.                 primenumbers.append(x)
    
20.         x += step
    
21.         step = 4 if step == 2 else 2
    
22. 
    
23.     return count
    
24. 
    
25. lst=[]
    
26. n=input()
    
27. while n:
    
28.     n=int(n)
    
29.     lst.append(n)
    
30.     n=input()
    
31. for n in lst:
    
32.     print(func_get_prime(n))

复制代码

一分钟行不行

逃兵

1. def get_primes(n: int) -> list:
   
2.     """
   
3.     return a list containing all prime numbers less than n.
   
4.     """
   
5.     if n <= 2:
   
6.         return []
   
7.     isprime = [True for _ in range(n)]
   
8.     result = [2]
   
9.     for i in range(3, n, 2):
   
10.         if isprime[i]:
    
11.             result.append(i)
    
12.         for j in range(0, len(result)):
    
13.             if i * result[j] >= n:
    
14.                 break
    
15.             isprime[i * result[j]] = False
    
16.             if i % result[j] == 0:
    
17.                 break
    
18.     return len(result)
    
19. 
    
20. lst=[]
    
21. n=input()
    
22. while n:
    
23.     n=int(n)
    
24.     lst.append(n)
    
25.     n=input()
    
26. for n in lst:
    
27.     print(get_primes(n))
    

复制代码