python 3.x中的遞歸is_prime函數

在我學校的計算機科學2課上，我們正在探索遞歸。我們已經使用遞歸來進行階乘或Fibonacci序列的處理，但是卡在is_prime(n)函數中，如果n爲素數則返回True，否則返回False。我們之前曾經迭代地寫過一篇，但似乎無法弄清楚如何遞歸地做。這是我們到目前爲止：python 3.x中的遞歸is_prime函數

def is_prime(n): 

    if n < 2: return False 
    #1 or 0 is not prime, base case 1 

    if n == 2 or n == 3: return True 
    #2 and 3 are both prime, base case 2 

    if is_prime(n-1): return False 
    #This checks if n-1 is prime, b/c if so then n must not be prime 
    #However, this only works b/c the first few numbers have lots of primes 

    return True 
    #Only returns True if nothing else has returned

如果任何人可以幫助我們一點點，最好通過只是一些提示，這將是偉大的。謝謝！

來源

2016-05-15 dyawata18

那麼如果'n-1'是素數和'n> 3'那麼'n'是複合的。除了那種微不足道的觀察之外，知道'n-1'會發生什麼情況，告訴你很少有關於'n'的信息。沒有很好的方法來減少檢查'n'是否是檢查'n-1'是否爲素數的主要問題。 –

說實話，我不認爲這是遞歸的好選擇。迭代解決方案將更加簡單快捷。我意識到你在這件事上沒有選擇，但是，對我來說，這似乎是一個愚蠢的任務。 –

@TomKarzes我同意在Python（或大多數語言）中做這件事情沒什麼意義，但有像Lisp這樣的語言，其中大多數計算是遞歸地完成的。一門很好的計算機科學入門課程應該讓學生接觸到各種範例，因此作爲一種學習練習來弄清楚如何遞歸地做這樣的事情是有意義的。 –

is_prime(n-1)在計算is_prime(n)時不是非常有幫助。相反，遞歸方法會在執行大部分計算的輔助函數中進行遞歸。

喜歡的東西no_divisors(n,k)其計算結果爲True如果範圍2，3，...，k不包含的n除數。很容易看到no_divisors(n,k)可以減少到no_divisors(n,k-1)。定義這個函數，然後根據它定義is_prime()。作爲優化，您可能需要首先檢查2和3的可分性作爲基本情況，然後查看奇數候選因子。

來源

2016-05-16 00:17:53

也許是遞增另一個值，反覆檢查你的n不是該值的倍數？像這樣：

開始與d爲上限

1）當d達到下界 - 返回false

2）如果d N的倍數 - 返回true

3）默認情況 - 遞減遞減d

您可以選擇下限和上限的含義。（例如，從2到n/2是最基本的方法）

另一種可能的低限上限方法可能是將d從sqrt（n）遞歸到2或甚至檢查除以2之前的除法並跳過一些值等...

來源

2016-05-16 00:15:19

確定素性的一個微不足道的方法是測試區間[2，sqrt（n）]中的所有整數x是否爲n % x == 0。遞歸地做到這一點：再次

如果n < x * x然後n是首要

開始我們x在2
檢查，如果n % x == 0
如果不是，增加x並調用is_prime功能

來源

2016-05-16 00:16:27 pzp

python 3.x中的遞歸is_prime函數

回答

相關問題