在Python中生成大素數

我似乎無法使用此代碼製作隨機素數，請有人可以幫助我嗎？在Python中生成大素數

def RandomPrime(): 
    prime = False 
    while prime == False: 
    n = random.randint(10000, 100000) 
    if n % 2 != 0: 
     for x in range(3, int(n**0.5), 2): 
     if n % x ==0: 
      prime = False 
     else: 
      prime = True 


    return n

來源

2014-01-10 user3181295

在'for'循環的每次迭代中，您忽略了早期迭代通過設置'prime = False'或'prime = True'告訴您的情況，而不考慮'prime'曾經是什麼。 – user2357112

正確的邏輯，您在設置True時n % x！ = 0首次：

for x in range(3, int(n**0.5), 2): 
    if n % x ==0: 
     prime = False 
    else: 
     prime = True

應該是：

prime = False 
    for x in range(3, int(n**0.5), 2): 
    if n % x ==0: 
     break 
    else: 
    prime = True

讀break and continue Statements, and else Clauses on Loops。

編寫等效代碼將是（來自@Steve Jesso）的短方式：

prime = all(n % x != 0 for x in range(3, int(n**0.5), 2)

來源

2014-01-10 11:25:54

OP只想在發現素數時返回，而不是返回False，它應該循環到一個新的隨機數。 – jonrsharpe

@jonrsharpe我困惑...所以請再次檢查... –

如果循環*不*中斷，'for'循環的'else'會執行，所以您應該在其中設置'prime = True'。但實際上你可以用'prime = all（n％x！= 0）代替整個事物（3，int（n ** 0.5），2）'。 –

看看的選項卡：其他應指整個for循環，而不是到IF

def RandomPrime(): 
    prime = False 
    while prime == False: 
    n = random.randint(10000, 100000) 
    if n % 2 != 0: 
     for x in range(3, int(n**0.5), 2): 
     if n % x ==0: 
      break 
     else: 
      prime = True 


    return n

來源

2014-01-10 11:29:22

考慮到循環甚至沒有「break」，這不是一個正確的答案。 – user2357112

有是錯誤在你的代碼：

不正確的「其他」;如果餘數不爲0，則不能聲明數字爲素數; 所有remaiders應該是非零
INT（N * 0.5）應該是int（N * 0.5 + 1），以防止上舍入誤差

的可能的解決方案是

def RandomPrime(): 
    while True: 
    n = random.randint(10000, 100000) 

    if n % 2 == 0: 
     continue; 

    prime = True; 

    for x in range(3, int(n**0.5 + 1), 2): 
     if n % x == 0: 
     prime = False; 

     break; 

    if prime: 
     return n

來源

2014-01-10 11:30:05

想象一下如果在range(3, int(n**0.5), 2)的最後數不是n整數除數：

if n % x ==0: 
    prime = False # not this 
else: 
    prime = True # this

所以即使所有以前的檢查評估False，你叫n一個素數。該最小改變了代碼解決這個問題是：

prime = prime and True # or 'prime &= True'

所以，如果prime是已經False，它仍然False。

但是，請記住，對於素數，如果這些檢查的任何是Falsen是不是質數。您可以使用此和Python的and和all（這是懶洋洋地評估，即不繼續檢查，一旦發現一個False），以更有效地實現：

def rand_prime(): 
    while True: 
     p = randint(10000, 100000) 
     if (r % 2 != 0 and 
      all(p % n != 0 for n in range(3, int(((p ** 0.5) + 1), 2))): 
      return p

爲了更好的性能，請注意randrange採用了step的論點，就像range，所以你可以跳過所有的偶數（這肯定不是素數！）：

def rand_prime(): 
    while True: 
     p = randrange(10001, 100000, 2) 
     if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)): 
      return p

注：sqrt(n)（從math），在我看來，更清晰以外，技術讀者少一點比n ** 0.5（雖然它may or may not be more efficient）。

來源

2014-01-10 12:05:12 jonrsharpe

非常好的答案。 –

在Python中生成大素數

回答

相關問題