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

zzzz

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