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

Tac

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

                               
登录/注册后可看大图

最佳答案

月排行榜 / 总排行榜

逃兵

2020-12-19 16:53:03

def get_primes(n: int) -> list:
    """
    return a list containing all prime numbers less than n.
    """
    if n <= 2:
        return []
    isprime = [True for _ in range(n)]
    result = [2]
    for i in range(3, n, 2):
        if isprime[i]:
            result.append(i)
        for j in range(0, len(result)):
            if i * result[j] >= n:
                break
            isprime[i * result[j]] = False
            if i % result[j] == 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))

跳转到最佳答案楼层

逃兵

import math
def func_get_prime(n):
  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))))
lst=[]
n=input()
while n:
    n=int(n)
    lst.append(n)
    n=input()
for n in lst:
    print(func_get_prime(n))

Tac

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

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

逃兵

1000
100000
10000000

168
9592
664579
>>> 

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

Tac

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

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

逃兵

def func_get_prime(n):
    count = 3
    primenumbers = [3,5]
    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 = [True for _ in range(n)]
    result = [2]
    for i in range(3, n, 2):
        if isprime[i]:
            result.append(i)
        for j in range(0, len(result)):
            if i * result[j] >= n:
                break
            isprime[i * result[j]] = False
            if i % result[j] == 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))