相关疑难解决方法(0)

为了测试一个数字是否为素数,为什么我们必须测试它是否只能被该数字的平方根整除？

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

只是我正在寻找的一个例子:我可以用一点代表每个奇数,例如对于给定的数字范围(1,10),从3开始:

__PRE__

以下字典可以挤得更对吗？我可以通过一些工作来消除五的倍数,但是以1,3,7或9结尾的数字必须在位数组中存在.希望这能澄清我想要的东西.

我正在寻找最好的算法,检查数字是否是素数,即布尔函数:

__PRE__

我想知道实现此功能的最佳算法.当然,我可以查询一个数据结构.我定义了最好的算法,它是生成数据结构的算法,该数据结构具有最低的内存消耗范围(1,N),其中N是常量.

检查给定大数是否为素数的最快方法是什么？我说的是大约10 ^ 32的数字.我从@MarcoBonelli的优秀答案中尝试了这个算法,它是:

from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

但它给出了Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize用于对抗如此大数字时的错误.那会是一个不同的,快速的方法呢？

def is_prime(num):
    lst = []
    if num > 1:
        pass
    else:
        return False
    for number in range(0, 1000000+1):
        if str(num) in str(number):
            continue
        elif str(1) in str(number):
            continue
        elif str(0) in str(number):
            continue
        lst.append(number)
    for x in lst:
        if num % num == 0 and num % 1 == 0 and not(num % x == 0):
            return True
        else:
            return False

print(is_prime(9))

我不知道我的代码有什么问题，我找不到解决方案，程序的重点是检查数字是否是素数（素数只能被 1 和它本身整除）。for 循环似乎不起作用或什么的