CS61A-lab03_Q5

Q5: It’s Always a Good Prime

Implement div_by_primes_under, which takes in an integer n and returns an n-divisibility checker. An n-divisibility-checker is a function that takes in an integer k and returns whether k is divisible by any integers between 2 and n, inclusive. Equivalently, it returns whether k is divisible by any primes less than or equal to n.

Review the Disc 01 is_prime problem for a reminder about prime numbers.

You can also choose to do the no lambda version, which is the same problem, just with defining functions with def instead of lambda.

Solution:

def div_by_primes_under(n):
    """
    >>> div_by_primes_under(10)(11)
    False
    >>> div_by_primes_under(10)(121)
    False
    >>> div_by_primes_under(10)(12)
    True
    >>> div_by_primes_under(5)(1)
    False
    """
    checker = lambda x: False
    i = 2
    while i < n:
        if not checker(i):
            checker = (lambda f, i: lambda x: x % i == 0 or f(x))(checker,i)
        i = i + 1
    return checker


def div_by_primes_under_no_lambda(n):
    """
    >>> div_by_primes_under_no_lambda(10)(11)
    False
    >>> div_by_primes_under_no_lambda(10)(121)
    False
    >>> div_by_primes_under_no_lambda(10)(12)
    True
    >>> div_by_primes_under_no_lambda(5)(1)
    False
    """
    def checker(x):
        return False
    i = 2
    while i < n:
        if not checker(i):
            def outer(f,i):
                def inner(x):
                    return x % i == 0 or f(x)
                return inner
            checker = outer(checker, i)
        i = i + 1
    return checker

Analysis:

核心理论依据：如果一个数不能整除以比它小的任何素数，那么这个数就是素数。^[1]

要求checker函数实现的功能就是判断k是否能整除以任何一个从2到n的素数，当然也就能同时实现判断一个数是否是素数。

根据一般想法，我们可以在div_by_primes_under_no_lambda函数里面定义一个normal_checker函数，使它对i从2到n逐个进行判断：满足i是素数且x % i == 0即可。示例如下：^[2]

def is_prime(x):
    '''Prime Number Judge'''
    i = 2
    while i * i < x:
        if x % i == 0:
            return False
        i += 1
    return True

def div_by_primes_under_no_lambda(n):
    def normal_checker(x):
        i = 2
        while i <= n:
            if is_prime(i) and x % i == 0:
                return True
            i += 1
        return False
    return normal_checker

理解此种一般做法之后，再来对官网给出的答案进行分析：

def div_by_primes_under_no_lambda(n):
    """
    >>> div_by_primes_under_no_lambda(10)(11)
    False
    >>> div_by_primes_under_no_lambda(10)(121)
    False
    >>> div_by_primes_under_no_lambda(10)(12)
    True
    >>> div_by_primes_under_no_lambda(5)(1)
    False
    """
    def checker(x):
        return False
    i = 2
    while i < n:
        if not checker(i):
            def outer(f,i):
                def inner(x):
                    return x % i == 0 or f(x)
                return inner
            checker = outer(checker, i)
        i = i + 1
    return checker

i的初始值为2，是素数，此时check(2)的值为False，直接进入while循环，if条件满足，定义嵌套函数outer和inner，接着checker函数被更新为outer(checker, i)的返回值，即return x % 2 == 0 or False，现在checker函数就能判断一个数是否能整除2。

i更新为3后，进入下一次循环，此时if语句中的checker函数返回值依旧是return x % 2 == 0 or False，刚好能判断3能否整除以任何一个比他小的任何素数(也就是2)，判断出3是素数。if条件满足，更新checker函数，使之能判断x是否能整除以素数3。注意，此时的checker函数返回值为return x % 3 == 0 or f(x)，这里的f(x)是i=2时的checker函数，也就等价于return x % 3 == 0 or False，也就是说，此时checker的返回语句等价于return x % 3 == 0 or x % 2 == 0 or False。

以此类推：i=4不是素数，不需要更新checker函数直接进入下次循环，i=5是素数，更新checker函数直到i=n，此时checker函数也更新为能够判断能否整除以2 ~ n的任何素数，即return x % k == 0 or...or...or...False(k是某个整数），是以or连接的一串整除判断语句，每一个f(x)都继承了上一轮循环的checker函数的返回值。

同理，简写的lambda表达式版函数也可以理解了。

Reference:

1. 5种你不知道的素数的判断方法 ↩
2. I Heard You Liked Functions… (CS61A作业笔记) ↩