质数,又称素数,指在大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。

求质数代码:

import math

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

>>> 455052511

其他方法

@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)


本文地址: http://www.chenxm.cc/article/949.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: Python 复数属性和方法操作实例
下一篇: 最常用的10个数据结构
发表评论

还没有留言,还不快点抢沙发?