如何從某個集合中獲取所有素數？

def all_primes(start,end): 
    list_nonprimes = [] 
    list_primes = [] 

    for i in range(start,end): 
     for a in range(2,i): 
      if i % a == 1 and i not in list_nonprimes: 
       if i not in list_primes: 
        list_primes.append(i) 
      else: 
       list_nonprimes.append(i) 

    return list_primes

爲什麼這給我一個不正確的輸出？如何從某個集合中獲取所有素數？

>>> all_primes(1,10) 
[3,5,7,9]

如何消除9？

來源

2012-11-17 Jacob Worldly

2被認爲是首要太 – xbonez

爲什麼遍歷'範圍（2,1）'當你已經把所有的素數小於'i'的名單？ – Amber

除此之外：您可能有興趣瞭解'any'和'all'。我想'如果沒有（對於list_primes中的i％a == 0）：list_primes.append（i）'讀取比'for-else'版本更好，儘管YMMV。 – DSM

有這樣做更直接的方式，因爲你本身已經產生質數列表不到你正在檢查數量：

def all_primes(start,end): 
    list_primes = [] 

    for i in range(2,end): 
     for a in list_primes: 
      if i % a == 0: 
       break 
     else: 
      list_primes.append(i) 

    return [x for x in list_primes if x >= start]

關鍵是理解這個是知道如何在for...else用Python構建工程。本質上，for循環可以有一個else語句，只有在循環評估期間沒有運行break語句時纔會執行該語句。

來源

2012-11-17 05:42:33 Amber

我不知道這個謝謝。你能否詳細介紹如何在for循環中使用else以及代碼的最後一行是什麼？ –

當然。 'for ... else'幾乎就是所描述的 - 它就像一個常規的'for'循環，然後如果for循環沒有'break'就結束'else'部分。最後一行是所謂的[列表理解]（http://docs.python.org/2/tutorial/datastructures.html#list-comprehensions）。 – Amber

更改它：

 if i % a == 1 and i not in list_nonprimes: 
      if i not in list_primes: 
       list_primes.append(i) 
     else: 
      list_nonprimes.append(i)

到：

 if i % a == 0 and i not in list_primes: 
      if i not in list_nonprimes: 
       list_nonprimes.append(i) 
     else: 
      list_primes.append(i)

旁白：你也可以考慮實施Sieve of Eratosthenes代替。理解起來相當直接，而且效率更高。

來源

2012-11-17 05:35:27

這看起來不對。 all_primes（1，10）現在返回[4,6,8]。也許'如果我％a！= 0 ...'？ – threenplusone

@threenplusone，sry，我還在編輯。你需要交換你的邏輯，因爲'i％a == 1'只是一個非素數的可能條件。你應該檢查，看看是否是一個主要的，並通過檢查'如果我％a == 0'消除它' –

我試着通過你的代碼來看看你哪裏錯了，但最終做了一些改變和優化。我已經評論了代碼，希望能夠解釋它自己。

def all_primes(start,end): 
    list_nonprimes = [] 
    list_primes = [] 

    for i in range(start,end): 
     # if already present in non_primes, skip 
     if i in list_nonprimes: continue 

     # if already present in primes, skip 
     if i in list_primes: continue 

     # if 2, mark it as prime. Special case 
     if i == 2 : 
      list_primes.append(i) 
      continue 

     # even numbers are not prime 
     if i%2 == 0: 
      list_nonprimes.append(i) 
      continue 

     # only check divisibility with odd numbers starting at 3 
     # and ending at sqrt(i) 
     for a in range(3,int(i**0,5)+1,2): 
      if i % a == 0 : 
       list_nonprimes.append(i) 
       break 

     # if we got here, and the number wasn;t added to non_primes 
     # it must be a prime 
     if i not in list_nonprimes: list_primes.append(i)    

    return list_primes 

start = 2 
end = 10 
print all_primes(start, end)

Demo

來源

2012-11-17 05:42:40 xbonez

如何從某個集合中獲取所有素數？

回答

相關問題