檢查數字是否是Python中的素數我寫了下面的代碼，應該檢查輸入的數字是否是素數，但是有一個問題我無法通過：def main():n = input("Please enter a number:")is_prime(n)def is_prime(a):
x = True
for i in (2, a):
while x:
if a%i == 0:
x = False
else:
x = True
if x:
print "prime"
else:
print "not prime"main()如果輸入的數字不是素數，則顯示“非素數”，因為它應該是，但如果數字是素數，則它不顯示任何內容。你能幫幫我嗎？
3 回答
楊__羊羊
TA貢獻1943條經驗 獲得超7個贊
以下是我對這個問題的看法：
from math import sqrt; from itertools import count, islicedef isPrime(n): return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
這是一個非常簡單和簡潔的算法，因此它并不意味著接近最快或最優的素數檢查算法。它的時間復雜度為O(sqrt(n))。頭以上這里了解更多關于做正確的素性測試和他們的歷史。
說明
我將給你一些關于將檢查素數的幾乎深奧的單行代碼的內容：
首先，使用
range()是一個壞主意，因為它會創建一個使用大量內存的數字列表。使用xrange()更好，因為它創建了一個生成器，它只需要記住你提供的初始參數，并在運行中生成每個數字。如果您使用的是Python 3或更高版本range()，則默認情況下已轉換為生成器。順便說一句，這根本不是最好的解決方案：嘗試調用xrange(n)一些n這樣的（這是C的最大值）。因此，創建范圍生成器的最佳方法是使用：n > 231-1longOverflowErroritertoolsxrange(2147483647+1) # OverflowErrorfrom itertools import count, islice count(1) # Count from 1 to infinity with step=+1islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3
n如果你想檢查是否n是素數，你實際上并不需要一直向前。你可以大大減少測試，只檢查2到√(n)（平方根n）。這是一個例子：讓我們找到所有除數
n = 100，并將它們列在表中：2 x 50 = 100 4 x 25 = 100 5 x 20 = 100 10 x 10 = 100 <-- sqrt(100) 20 x 5 = 100 25 x 4 = 100 50 x 2 = 100
你很容易注意到，在平方根之后
n，我們發現的所有除數實際上已經找到了。例如20已經發現了100/5。數字的平方根是我們發現的除數開始重復的確切中點。因此，要檢查數字是否為素數，您只需要從2到2進行檢查sqrt(n)。為什么
sqrt(n)-1呢，而不僅僅是sqrt(n)？那是因為提供給itertools.isliceobject 的第二個參數是要執行的迭代次數。迭代islice(count(a), b)后停止b。這就是為什么：for number in islice(count(10), 2): print number,# Will print: 10 11for number in islice(count(1, 3), 10): print number,# Will print: 1 4 7 10 13 16 19 22 25 28
該功能
all(...)與以下內容相同：def all(iterable): for element in iterable: if not element: return False return True
它確實檢查了所有數字
iterable，False當數字評估時返回False（這意味著只有數字為零）。那我們為什么要用呢？首先，我們不需要使用額外的索引變量（就像我們使用循環一樣），除此之外：只是為了簡潔，沒有真正需要它，但它看起來不那么笨重單行代碼而不是幾行嵌套行。
擴大的視野
我要包含一個“解壓縮”版本的isPrime()函數，以便更容易理解和閱讀它：
from math import sqrtfrom itertools import count, islicedef isPrime(n): if n < 2: return False for number in islice(count(2), int(sqrt(n) - 1)): if n % number == 0: return False return True
HUX布斯
TA貢獻1876條經驗 獲得超6個贊
有許多有效的方法可以測試primality（這不是其中之一），但你編寫的循環可以用Python簡潔地重寫：
def is_prime(a): return all(a % i for i in xrange(2, a))
也就是說，如果a和2之間的所有數字（不包括在內）在分成a時給出非零余數，則a為素數。
慕碼人2483693
TA貢獻1860條經驗 獲得超9個贊
如果您只有少量查詢，這是查看數字是否為素數的最有效方法。如果你問很多數字，如果他們是主要的嘗試Sieve of Eratosthenes。
import mathdef is_prime(n): if n == 2: return True if n % 2 == 0 or n <= 1: return False sqr = int(math.sqrt(n)) + 1 for divisor in range(3, sqr, 2): if n % divisor == 0: return False return True
添加回答
舉報
0/150
提交
取消