鱼C论坛

 找回密码
 立即注册
查看: 2736|回复: 6

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

[复制链接]
发表于 2020-12-19 10:40:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
为标准输入(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. lst=[]
  20. n=input()
  21. while n:
  22.     n=int(n)
  23.     lst.append(n)
  24.     n=input()
  25. for n in lst:
  26.     print(get_primes(n))
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2020-12-19 14:59:34 | 显示全部楼层
  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))
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-12-19 15:14:31 | 显示全部楼层

输入为10000000时没有输出什么情况啊
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-12-19 15:36:45 | 显示全部楼层
  1. 1000
  2. 100000
  3. 10000000

  4. 168
  5. 9592
  6. 664579
  7. >>>
复制代码

计算量大,运行时间长,一直等着就出来了
可接受的时间内,这个概念比较模糊,实际上需要的时间挺长的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

那可以通过编程缩短这个时间吗?要求是输入越大计算时间要尽可能短。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-12-19 16:40:00 | 显示全部楼层
  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.     return count

  23. lst=[]
  24. n=input()
  25. while n:
  26.     n=int(n)
  27.     lst.append(n)
  28.     n=input()
  29. for n in lst:
  30.     print(func_get_prime(n))
复制代码


一分钟行不行
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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. lst=[]
  20. n=input()
  21. while n:
  22.     n=int(n)
  23.     lst.append(n)
  24.     n=input()
  25. for n in lst:
  26.     print(get_primes(n))
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-30 03:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表