用于查找素数的Python循环

作为Python的第一个练习，我试图编写一个使用循环来查找素数的程序。一切工作与for循环，所以我想使用一个while循环。这有效，但程序返回一些不正确的数字。用于查找素数的Python循环

import math 
# looking for all primes below this number 
max_num = int(input("max number?: ")) 

primes = [2] # start with 2 
test_num = 3 # which means testing starts with 3 

while test_num < max_num: 
    i = 0 
    # It's only necessary to check with the primes smaller than the square 
    # root of the test_num 
    while primes[i] < math.sqrt(test_num): 
     # using modulo to figure out if test_num is prime or not 
     if (test_num % primes[i]) == 0: 
      test_num += 1 
      break 
     else: 
      i += 1 
    else: 
     primes.append(test_num) 
     test_num += 1 

print(primes)

因此，奇怪的是，为max_num=100返回：

[2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

这是除了9，25和49，我想不通为什么正确的。

来源

2016-01-07 Thomas

'primes [i] <= math.sqrt（test_num）' – vesche

您是否注意到数字是奇数？ – njzk2

A'while ... else'！记得当它进入'else'后有乐趣（我不知道其他人，但我一直避免'while-else'和'for-else'，并且从未在其他人的代码中看到过他们;他们感觉不直观） – dwanderson

你需要去和包括平方根。否则你的算法将会错过素数正方形的家族（9,25和49是素数正方形）。

快速解决方法是用<=替代<作为停止条件。

但考虑改变停止条件

primes[i] * primes[i] <= test_num

有了这个测试，你不沾进出的浮点运算。

来源

2016-01-07 20:01:20 Bathsheba

如果你想为每次迭代找到下一个素数，可能这是一个更好的函数，因为它绕过了给定输入的过程。

import math 
def primes(): 
    (h,n) = (2,1) 
    k = 2 
    while True: 
     if any(k % i == 0 for i in range(2,k))==False: # h is composite number, so continue iteration 
      (h,n) = (k,n+1) # After the for loop we can find out the next prime number 
      k += 1 
     else: 
      k += 1 # Remember to continue the loop, if not then next function may return the same number 
      continue   
     yield h 
x = prime()

然后你可以使用如下迭代：

next(x)

或

[next(x) for _ in range(20)]

这给输出

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

希望这是一个书写优美的功能而素数目标的循环在初学者。

来源

2018-02-18 07:29:11 son520804

用于查找素数的Python循环

回答

相关问题