计算素数并追加到列表

Question

我最近开始尝试使用python解决项目Euler上的问题，并且在尝试计算素数并将它们附加到列表时遇到了这个道路颠簸。我写了下面的代码，但我很困惑，为什么它在运行时不输出任何内容。

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) 

Answer 1

尝试：

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) 

Answer 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] 

Answer 3

使用条件列表理解：

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] 

Answer 4

最简单的方法是使用称为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。另外，为了优化，我们只迭代100万的平方根。为什么这样？因为一个数字不能有两个因素都大于数字的平方根。因此，如果我们将整数除以整数直到其平方根的上限，而且它仍然不可分割，那就意味着它是一个素数。

所以，如果你想检查一个数字是否为素数，你可以简单地使用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 

对于10万个的数字，用筛快12倍以上。对于一百万比例变为90.而且，当使用这么多数字时，我会建议不要追加列表。相反，启动一个列表然后分配值。

Answer 5

如果您正在构建素数列表，将该列表用作解决方案的一部分效率会更高。

例如，这个循环：

for i in range(3, int(math.sqrt(number)) + 1): 

对于素1009将测试〜30个的数字，但只有10个素数小于1009的平方根实际上需要进行测试。而这种差异正在不断增加。

使用我们的增长主要列表作为解决方案的一部分：

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的筛子，但许多其他的解决方案之前，将有可能完成。

Answer 6

现在它的工作原理，我已经shortned的编号，以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) 

[OUTPUT]：

[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，34 7，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]

Answer 7

在[0,9999999]中获得所有素数的算法效率不高。它需要花很长时间才能完成，以便在执行时不会看到输出。这只是因为它没有完成。对于更快的算法，您可能会检查this列出