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

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))
    

复制代码

跳转到最佳答案楼层

Tac

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

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

Tac

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

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