python - 使用 Numpy 进行更快的计算

Question

我有这个程序可以列出一定范围内的质数。问题是数字越大，它变得越慢。我如何使用 numpy 来提高速度？如果不是 numpy，有没有其他方法可以加快计算速度？

from datetime import date
import time
import numpy as np

today = date.today()

lower = int(input("Starting Number: "))
upper = int(input("Ending Number: "))

print("Prime numbers between",lower,"and",upper,"are:")
with open("primenumbers.txt","a") as file:
    file.write("\n")
    file.write("{}".format(today))
    file.write("\n")

start = time.time()

for num in range(lower,upper + 1):
   if num > 1:
       for i in range(2,num):
           if (num % i) == 0:
               break
       else:
         print(num)
         with open("primenumbers.txt","a") as file:
             file.write("\n")
             file.write("{}".format(num))
end = time.time()
print(end - start)

我想更快地处理数据，请显示一些代码。

Answer 1

筛法是寻找素数的有效方法之一。我的回答灵感来自 this在 SO 中回答。对于 100 万，我得到了 timeit

16 ms ± 3.68 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

Numpy 实现

def first_n_prime_numbres(n):    
    s = np.arange(3, n, 2)
    for m in range(3, int(n ** 0.5)+1, 2):         
        if s[(m-3)//2]: 
            s[(m*m-3)//2::m]=0
    return np.r_[2, s[s>0]]

first_n_prime_numbres(100)