首页 > 试题广场 > 假设可以不考虑计算机运行资源(如内存)的限制,以下 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
这是一个求质数个数的题不说了
简单做一个递归的优化,每次都用质数筛
@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 回复(4)
本题是求0-100亿之间的素数的个数,首先你要读懂代码。
读懂代码后,自己编写Meissel-Lehmer 算法快速求出0-100亿内的素数个数。
关于楼上说的网上百度100亿以内的素数,我没有百度到。但是我们可以记住这个值
关于Meissel-Lehmer算法可以按照名字自行查找资料。
延申练习题参考HOJ 杭电OJ 5901题   counting prime
发表于 2019-06-09 15:20:29 回复(0)
函数的返回值是不大于参数的质数个数。(优化空间极大...
发表于 2019-04-09 10:45:20 回复(3)
并没看懂是什么意思,蒙对了
发表于 2019-08-30 21:44:36 回复(2)
这道题,不能硬做,直接拿到python上跑,肯定会jj,要读懂代码的内涵。当然也可以先跑几个简单的例子,比如跑print(sieve(10))或者print(sieve(100))等等。其实,如果学过素数筛的就能很快看出,这是一道素数筛选的题。所以我们只要上网直接搜一下10000000000以内的素数个数就可以了。
发表于 2019-04-13 19:56:06 回复(4)

先建一个100亿大小的列表,把每个元素都设置为true表示不是质数,最后统计false的个数

发表于 2020-02-21 00:13:42 回复(0)

完全是懵的

发表于 2020-02-20 00:32:44 回复(0)
能看懂是在筛素数,最后求N以内的素数的个数。不过肯定不能直接按这个代码跑,100亿的列表,直接报MemoryError了!  
N比较小的时候,再烂的算法怎么也能跑出来,N很大的时候,没有好的算法还是不要轻易尝试了😂😂。
我等小白还是先略过吧...
发表于 2020-02-12 11:15:00 回复(0)
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(100))

发表于 2020-01-16 15:49:23 回复(0)
怎么会有这种题,求100亿以内的质数个数,我求的出来我还会在这做题??
发表于 2019-10-31 11:04:51 回复(0)
读懂代码,排除法,其它几个都不是素数
发表于 2019-10-24 19:53:03 回复(1)
大神们,这道题我怎么运行,结果都是2呀。我都不知道我哪儿敲错了
发表于 2019-10-16 17:27:44 回复(0)

zzzz

发表于 2019-08-30 17:10:33 回复(0)