在 python 中寻找质数

Question

我知道 python 是 "slow as dirt"，但我想制作一个快速高效的程序来查找素数。这就是我所拥有的：

    num = 5 #Start at five, 2 and 3 are printed manually and 4 is a        multiple of 2
    print("2")
    print("3")

def isPrime(n):
#It uses the fact that a prime (except 2 and 3) is of form 6k - 1 or 6k + 1 and looks only at divisors of this form.

    i = 5
    w = 2
    while (i * i <= n): #You only need to check up too the square root of n
        if (n % i == 0): #If n is divisable by i, it is not a prime
            return False
        i += w
        w = 6 - w
    return True #If it isn´t ruled out by now, it is a prime


while True:
    if ((num % 2 != 0) and (num % 3 != 0)): #save time, only run the     function of numbers that are not multiples of 2 or 3
        if (isPrime(num) == True):
            print(num) #print the now proved prime out to the screen
    num += 2 #You only need to check odd numbers

现在我的问题来了：
- 这会打印出所有素数吗？
- 这会打印出任何不是素数的数字吗？
-是否有更有效的方法（可能有）？ -这会走多远（python的限制），有什么方法可以提高上限吗？

使用 python 2.7.12

Answer 1

Does this print out ALL prime numbers?

正如欧几里德在公元前 300 年左右证明的那样，素数有无穷多个。所以这个问题的答案很可能是否定的。

Does this print out any numbers that aren't primes?

从表面上看，事实并非如此。但是，可以肯定的是；为什么不写一个单元测试？

Are there more efficient ways(there probably are)? -How far will this go(limitations of python), and are there any ways to increase upper limit?

见Fastest way to list all primes below N or Finding the 10001st prime - how to optimize?

Answer 2

检查 num % 2 != 0 即使每次递增 2 似乎毫无意义。

我发现这个算法更快：

primes=[]

n=3

print("2")
while True:
    is_prime=True
    for prime in primes:
        if n % prime ==0:
            is_prime=False
            break
        if prime*prime>n:
            break

    if is_prime:
        primes.append(n)
        print (n)

    n+=2

Answer 3

这个很简单。下面的函数returns True 如果num 是素数，否则False。在这里，如果我们找到一个因子，而不是 1 和它本身，那么我们会提前停止迭代，因为这个数字不是素数。

def is_this_a_prime(num):
    if num < 2 : return False # primes must be greater than 1
    for i in range(2,num): # for all integers between 2 and num
        if(num % i == 0): # search if num has a factor other than 1 and itself
            return False # if it does break, no need to search further, return False
    return True # if it doesn't we reached that point, so num is a prime, return True

Answer 4

我尝试稍微优化一下代码，这就是我 done.Instead 的运行循环 n 或 n/2 次，我已经使用一个条件语句。（我认为它更快一点）

def prime(num1, num2):
import math
def_ = [2,3,5,7,11]
result = []
for i in range(num1, num2):
    if i%2!=0 and i%3!=0 and i%5!=0 and i%7!=0 and i%11!=0:
        x = str(math.sqrt(i)).split('.')
        if int(x[1][0]) > 0:
            result.append(i)
    else:
        continue

return def_+result if num1 < 12 else result

在 python 中寻找质数

Finding primes in python

python

math

performance

primes

python-2.7