首页 > 试题广场 >

假设可以不考虑计算机运行资源（如内存）的限制，以下 pyth

[单选题]

假设可以不考虑计算机运行资源（如内存）的限制，以下 python3 代码的预期运行结果是：（）

import math
def sieve(size):
    sieve= [True] * size
    sieve[0] = False
    sieve[1] = False
    for i in range(2, int(math.sqrt(size)) + 1):
        k= i * 2
        while k < size:
           sieve[k] = False
           k += i
    return sum(1 for x in sieve if x)
print(sieve(10000000000))

```
455052510
```
```
455052511
```
```
455052512
```
```
455052513
```

查看正确选项

Anascetic

怎么会有这种题，求100亿以内的质数个数，我求的出来我还会在这做题？？

发表于 2019-10-31 11:04:51 回复(19)

小黄人的黄

本题是通过排除法找素数的个数，以size为20为例，算法的思想就是先假设size以内的所有的数都为素数(sieve = [True] * size),然后在找到size以内的所有的因数(2,math.sqrt(size)+1)p排除掉所有因数的乘数(sieve[k]=False)，剩下的就是size内所有的素数。

math.sqrt(size)+1 为size以内的所有数的最大公因数。

发表于 2020-07-18 15:28:25 回复(8)

青春带笑work

http://sweet.ua.pt/tos/bib/5.4.pdf

发表于 2020-04-29 10:43:59 回复(5)

AngusZhu

这是一个求质数个数的题不说了

简单做一个递归的优化，每次都用质数筛

@numba.jit()
def cur(size):
    sieve = [True] * size
    sieve[0] = False
    sieve[1] = False
    if size == 2:
        return sieve
    factor = [index for index, val in enumerate(cur(int(math.sqrt(size)+1))) if val]
    for i in factor:
        k = i * 2
        while k < size:
            sieve[k] = False
            k += i
    return sieve

def up(size):
    sieve = cur(size)
    return sum(1 for x in sieve if x)

关键在于

@numba.jit()

这一行，用了numba的及时解释器，把cur函数重新编译了。

在我的mac上大概10分钟不到就可以出结果。

很多数值计算在python 里面超级慢，但是用了numba的jit基本可以和c的效率同一数量级。

并且写起来很方便，可以尽情地写for循环，方便jit理解，实际运行效率更高。

用tensorflow写了神经网络顺便想用python简单处理一下数据，但是又被python的效率限制的童鞋可以尝试一下。

我自己实测超级好用。（其实是我不会写c，233

编辑于 2019-05-12 17:00:09 回复(8)

谜の咸鱼

函数的返回值是不大于参数的质数个数。（优化空间极大...

发表于 2019-04-09 10:45:20 回复(4)

陌安

#这个地方以100举例
import math
def sieve(size):
    sieve= [True] * size
    sieve[0] = False
    sieve[1] = False#这100个数除了0和1其余默认为True
    for i in range(2, int(math.sqrt(size)) + 1):#从2开始一直到10
        k= i * 2
        while k < size: 
           sieve[k] = False
           k += i#4为首项，公差为2的数为False;6为首项公差为3的数，以此类推，直到20为首项公差为10的数
    return sum(1 for x in sieve if x)#统计True的个数
print(sieve(100))

我不明白的是，这题一般笔记本根本跑不出来，就算知道能算出素数的个数，考试的时候我咋知道答案是什么？

编辑于 2020-02-25 16:07:03 回复(1)

MAKEIT20180506214273

本题是求0-100亿之间的素数的个数，首先你要读懂代码。

读懂代码后，自己编写Meissel-Lehmer 算法快速求出0-100亿内的素数个数。

关于楼上说的网上百度100亿以内的素数，我没有百度到。但是我们可以记住这个值

关于Meissel-Lehmer算法可以按照名字自行查找资料。

延申练习题参考HOJ 杭电OJ 5901题 counting prime

发表于 2019-06-09 15:20:29 回复(1)

牛客257354664号

当我写了写发现是要求质数个数后整个人都不好了…… 冲着玄学我开始分析答案中的数哪个比较像质数，首先ac能被2整除，排除。 d的数字加起来能被3整除，排除。所以选b。我遁了

发表于 2020-08-19 21:53:57 回复(2)

Better-M

这道题，不能硬做，直接拿到python上跑，肯定会jj，要读懂代码的内涵。当然也可以先跑几个简单的例子，比如跑print(sieve(10))或者print(sieve(100))等等。其实，如果学过素数筛的就能很快看出，这是一道素数筛选的题。所以我们只要上网直接搜一下10000000000以内的素数个数就可以了。

发表于 2019-04-13 19:56:06 回复(6)

Noah4

筛法求10000000000以内的素数，初始化时认为所有数都是素数，然后以2为开头，2的倍数全部都不是素数，碰到3为True，3的倍数也全部置为False，以此类推

但要是笔试考这题，不查表能做出来我倒立喝可乐！

编辑于 2020-11-07 14:18:38 回复(1)

轶群

并没看懂是什么意思，蒙对了

发表于 2019-08-30 21:44:36 回复(2)

牛客689600338号

判断n是不是素数,只需整除一遍2至n的算术平方根即可,如果出现整除的情况,则不是素数.可以认为因数是成对出现的,比如100,10就是分界点,所有成对的因数分布在10的左右,2到10的所有数就已经包含了所有可能的因数对.

发表于 2022-04-08 18:19:17 回复(0)

viod

答案：455052511

先要读懂题目给定代码的功能，很简单：求出100亿内的质数个数。然后问题就来了，求解用到了递归，需要开辟非常大的内存空间栈，加上巨大的运算量，咱学生党的电脑跑出来不容易，因此需要自己优化代码求解（可以考虑使用python的numba加速loop，用法：https://zhuanlan.zhihu.com/p/60994299）

发表于 2020-11-08 12:44:01 回复(0)

躺不平站不直跑不动

这道题就是统计100亿内质数的个数
使用的方式是埃氏筛

埃式筛法的思路非常简单，就是用已经筛选出来的素数去过滤所有能够被它整除的数，最后剩下的数就是素数

就本本题来说查表最快

想了解埃氏筛的可以看这篇博客https://blog.csdn.net/qq_52007481/article/details/124002014

我自己写的埃氏筛

用这个埃氏筛求1亿以内的质数大约是3分钟左右

10亿以内的质数的个数大约需要用8分钟左右

用算法的角度来说就是用空间换时间，数的范围越大需要的内存空间就越大，像100亿这个范围一般的电脑算不出来

n = 10**8  # 代求的范围中的最大值
k = 0
s = [True for i in range(n)]  # 首先默认所有数都是质数
for i in range(2,n):
    if s[i]:  # 判断是否为质数，如果没有被标记过，就是质数
        k+=1
        # 这个for循环和while循环的作用一样
        for j in range(i+i,n,i):   # 将是指数的倍数的数都改为False
            s[j] = False
print(k) # 个数

编辑于 2022-08-14 17:48:33 回复(0)

拧断的钥匙

这道题总感觉应该是 sum([1 for x in sieve if x]) 或 sum((1 for x in sieve if x)) 才对，毕竟 sum 中要传入一个可迭代对象，这种但是不加[] 或()也可以,所以我感觉可能是 sum函数本身将1 for x in sieve if x包装成了一个迭代器对象。

发表于 2022-06-03 17:05:59 回复(1)