如何找到一个有上限的质数并存储在数组中？

Question

所以我试图找到一个质数，并将其存储在一个数组中。我查看和搜索的内容有些令人困惑，而我老师的解释本身也令人困惑。他的伪代码是 confusing 而我目前的代码是

prime = [False,False]
anumber = int(input("Enter the upper bound number: "))

print("generating all primes between 2 and ", anumber)

j=0
while anumber > j:
    for j in range(2,anumber):
        if(anumber % j ) ==0:
            print(j,"is not prime")
            prime.append(False)
        else:
            print(j,"is prime")
            prime.append(True)
print(prime)

我是编程新手，这真让我头疼。我的老师放在他的网站上的输出和我得到的输出是 here。他们一点都不像，但我不明白我做错了什么？

Answer 1

你的第一个问题是你的 while anumber > j:，j 在任何时候都不会增加，所以你有一个无限循环。

接下来伪代码不需要取模 (%)，因为它是 prime sieve。质数筛去除所有不能为质数的数字；在你的算法的情况下是素数的倍数。

您需要遍历所有数字并删除所有素数的倍数。您也不应附加 True/False，而应根据数字是否为质数更改标记。

请注意合数不是质数

以下代码是基于给出的伪代码的工作素筛。

upperBound = input("Enter the upper bound number: ")

"""Create a list named prime of booleans, all set to True, for numbers between 0 and the upper bound"""
prime = [True]*(upperBound + 1) #List of booleans all set to True


"""set prime[0] and prime[1] to False"""
prime[0] = False #0 is not prime
prime[1] = False #1 is not prime

print "Generating all primes between 2 and", upperBound

"""let p loop over all values between 2 and the upper bound (inclusive)"""
for p in range(2, upperBound + 1): #Loop through all the values between 2 and the upper bound, inclusive
    print "Checking", str(p)
    if prime[p] == True: #if the number is prime
        k = p + p #k is the first multiple of the prime number
        print " ", str(p), "is prime"
        for x in range(k, upperBound + 1, p): #Iterate through all the multiples of the prime, less than the upper bound
            print " ", str(x), "is not prime"
            prime[x] = False #Mark the multiples as composite

"""The prime list now has a True value for those numbers that are prime"""

"""Generate the result list with a loop adding numbers to the list"""
primeNumbers = []
for x in range(len(prime)): #Iterate through the boolean list
    if prime[x] == True: #if the number is prime
        primeNumbers.append(x) #add it to the list of prime numbers

print primeNumbers

该算法的效率并不高，因为一旦达到上限的一半 + 1，所有合数都已找到。您还应该注意，此筛子不适用于非常大的上界。

例如上限 = 10

一旦 p = 6，p 的倍数（12、18、24...）都在上限以上，因此您现在正在浪费处理时间，因为 for 循环不会 return 任何数字。

>>> range(12, 11, 6)
[]
>>>

所以可以通过替换

来改进算法

for p in range(2, upperBound + 1): #Loop through all the values between 2 and the upper bound, inclusive

和

for p in range(2, (upperBound/2) + 1): #Loop through all the values between 2 and half the upper bound + 1

原始版本（上限 = 100）：2.39502692223

新版本（上限 = 100）：1.88608288765

主要原因是印刷量少。

可以找到上限 100 的示例输出 here，这是使用更高效的版本。

如何找到一个有上限的质数并存储在数组中？

How to find a prime number with an upperbound and store in an array?

python

arrays

numbers