求大佬帮忙 质数问题
为标准输入（stdin）的每一行给定一个正整数，需要输出不超过该整数的质数个数。当输入文本为空行时，程序必须完成。要求：可以使用Eratosthenes’s筛算法，另外该问题中对计算速度要求较高，这意味着代码应该尽可能快地回答更大的数字情况。
也就是说代码需要能在可接受的时间内正确地回答像100000或10000000这样的大数的情况。
请将编码的主要思路记录在备注中。
下图为输入输出示例
https://iknow-pic.cdn.bcebos.com/caef76094b36acaf168d8d836cd98d1001e99c5b?x-bce-process=image/resize,m_lfit,w_600,h_800,limit_1 import math
def func_get_prime(n):
return len(list(filter(lambda x: not , range(2,n+1))))
lst=[]
n=input()
while n:
n=int(n)
lst.append(n)
n=input()
for n in lst:
print(func_get_prime(n)) 逃兵 发表于 2020-12-19 14:59
输入为10000000时没有输出什么情况啊 1000
100000
10000000
168
9592
664579
>>>
计算量大，运行时间长，一直等着就出来了
可接受的时间内，这个概念比较模糊，实际上需要的时间挺长的 逃兵 发表于 2020-12-19 15:36
计算量大，运行时间长，一直等着就出来了
可接受的时间内，这个概念比较模糊，实际上需要的时间挺长的
那可以通过编程缩短这个时间吗？要求是输入越大计算时间要尽可能短。 def func_get_prime(n):
count = 3
primenumbers =
x = 7
step = 4
while x < n:
flag = False
j = int(x ** 0.5)
if x % 5 != 0:
for i in primenumbers:
if i > j:
flag = True
break
if x % i == 0:
flag = False
break
if flag:
count += 1
primenumbers.append(x)
x += step
step = 4 if step == 2 else 2
return count
lst=[]
n=input()
while n:
n=int(n)
lst.append(n)
n=input()
for n in lst:
print(func_get_prime(n))
一分钟行不行 def get_primes(n: int) -> list:
"""
return a list containing all prime numbers less than n.
"""
if n <= 2:
return []
isprime =
result =
for i in range(3, n, 2):
if isprime:
result.append(i)
for j in range(0, len(result)):
if i * result >= n:
break
isprime] = False
if i % result == 0:
break
return len(result)
lst=[]
n=input()
while n:
n=int(n)
lst.append(n)
n=input()
for n in lst:
print(get_primes(n))
页:
[1]