logo标签列表

计算质数并将其添加到列表中

pythonlistprimes
6

我最近开始尝试使用python解决项目欧拉中的问题，在尝试计算质数并将它们添加到列表时遇到了障碍。我编写了以下代码，但当我运行它时，我很困惑为什么它没有输出任何东西。

import math

primes = []

def isPrime(i):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for i in range(3,int(sqrt(number))+1):
        if number%i==0:
            return False
    return True

for i in range (1, 9999999):
    if isPrime(i) == True:
        primes.append(i)
    else:
        continue
print(primes)
1
首先将def isPrime(i):更改为def isPrime(number):，并将for i in range(3,int(sqrt(number))+1):更改为for i in range(3,int(math.sqrt(number))+1): - jacoblaw
1
这是一种非常低效的计算质数列表的方法。最好直接使用筛法生成质数。 - AChampion
嗯...它能运行吗？i 应该是 number，sqrt 应该是 math.sqrt。 - Andrea Corbellini
1
当你在Python中使用for循环时，几乎肯定是错误的。Python的方法是使用列表推导式：primes = [i for i in range(1, 9999999) if isPrime(i)]。 - DYZ
你说得非常正确，@DYZ。这正是我要评论的，它比向空列表附加更有效，并且是一种更简洁的语句。 - Joe Iddon
7个回答
4
尝试：
import math

primes = []

def isPrime(number):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for i in range(3,int(math.sqrt(number))+1):
        if number%i==0:
            return False
    return True

for i in range (1, 9999999):
    if isPrime(i) == True:
        primes.append(i)

print(primes)
1
注意：else: continue 不是必要的。 - Andrea Corbellini
修复了 @AndreaCorbellini。 - Md. Rezwanul Haque
2

试试这个：

import math

primes = []

def isPrime(number):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for ind in range(3,int(math.sqrt(number))+1):
        if number%ind==0:
            return False
    return True

for i in range (1, 100):
    if isPrime(i) == True:
        primes.append(i)
    else:
        continue

print(primes)

为了展示它的工作原理，我打印出前100个:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
2

最简单的方法是使用称为筛子（Sieve）的东西。以下是获取所有小于一百万的质数的方法。

def mark_sieve(sieve, x):
    for i in range(x+x, len(sieve), x):
        sieve[i] = False

sieve = [True]*(10**7+1)
for x in range(2, int(len(sieve)**0.5 + 1)):
    if sieve[x]: mark_sieve(sieve, x)

这段代码的思路是，我们首先创建一个名为sieve的列表，并将所有值赋为True，这意味着我们暂时将1百万（包括在内）以内的所有数字视为质数。我们将遍历一百万个数字，并标记sieve列表中它的每个倍数为False。此外，为了优化，我们只迭代到1百万的平方根。为什么？因为一个数字不能有两个因子都大于该数字的平方根。因此，如果我们将一个数字除以小于其平方根的整数并且仍然不可除尽，那么它就是质数。

因此，如果您想检查一个数字是否为质数，可以简单地使用sieve[some_number]。如果返回False，则不是质数。要获取质数列表，可以使用[x for x in range(len(sieve)) if sieve[x]]

编辑 速度比较 - 

import timeit
import math

def isPrime(number):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for ind in range(3,int(math.sqrt(number))+1):
        if number%ind==0:
            return False
    return True

def mark_sieve(sieve, x):
    for i in range(x+x, len(sieve), x):
        sieve[i] = False


# Other approaches
time_0 = timeit.default_timer()
primes = []
for i in range (1, 10**6+1):
    if isPrime(i) == True:
        primes.append(i)
    else:
        continue

# Sieve Approach
time_1 = timeit.default_timer()
sieve = [True]*(10**6+1)
sieve[0] = False #because we wont consider zero and one as primes
sieve[1] = False
for x in range(2, int(len(sieve)**0.5 + 1)):
    if sieve[x]: mark_sieve(sieve, x)

primes_2 = [x for x in range(len(sieve)) if sieve[x]]

time_2 = timeit.default_timer()
time_1-time_0 # 12.423080921173096 seconds
time_2-time_1 # 0.9901950359344482 seconds

对于一百万个数字，使用筛法要快12倍以上。对于一百万个数字，比值变成了90。此外，在使用这么多数字时，我建议不要将列表附加到一起。相反，初始化一个列表，然后再赋值。
1
这种方法比其他方法快得惊人。然而，它在边缘处需要进行一点点清理，因为它声称0和1是质数... - cdlane
@cdlane，是的，我跳过了那个。已做出更改。谢谢！ - Clock Slave
2
如果您正在构建素数列表，将该列表作为解决方案的一部分可能更有效。
例如，以下循环：
for i in range(3, int(math.sqrt(number)) + 1):

对于质数1009，需要测试大约30个数字，但是小于1009平方根的质数只有10个需要测试。这个差距会不断增加。

使用我们不断增长的质数列表来作为解决方案的一部分：

primes = [2]

for number in range(3, 9999999 + 1, 2):  # only test odd numbers

    for prime in primes:
        if prime * prime > number:  # we're past sqrt, a prime!
            primes.append(number)
            break

        if number % prime == 0:  # a composite
            break

print(*primes[:10], '...', *primes[-10:])

虽然不及@ClockSlave的筛选算法快，但可能会在其他解决方案之前完成。

1
使用条件列表推导式：
primes = [
    i for i in range(1, 9999999) 
    if i == 2 
    or i > 2  # Anything less than 2 is not prime.
    and i % 2  # No evens (except for 2 above)
    and all(i % n for n in range(3, int(i ** 0.5) + 1))]

>>> primes[:10]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

>>> primes[-10:]
[9999889,
 9999901,
 9999907,
 9999929,
 9999931,
 9999937,
 9999943,
 9999971,
 9999973,
 9999991]
1
您的获取[0,9999999]中所有质数的算法效率不太高。执行时需要很长时间，以至于无法看到输出结果。这只是因为还没有完成。如果想要更快的算法，可以查看this。
1
现在它可以工作了，我将数字缩短为999。
import math

primes = []


def isPrime(number):
    if number <= 1:
        return False
    for i in range(2, int(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

for i in range(1, 999):
    if isPrime(i):
        primes.append(i)

print(primes)

[输出]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接