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函数

回答

相关问题