Returns 是 x 的约数的最小质数

Question

以下代码包含一个可以触发无限循环的错误，我无法弄清楚如何将第二个打印语句发送到运行，我相信修复它很简单，但只是看不到。

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    while n <= x:
        if x % n == 0:
            x += 1
            return n

print(smallest_prime_factor(12)) # should be 2
print(smallest_prime_factor(15)) # should be 3

Answer 1

不是增加 x 的值，这是您试图找到最小质数因数的数字，您需要增加 n 的因数。此外，如果 n 除 x，则您需要 return n 否则您需要在 if 块之外增加 n 的值.

试试这个代码：

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    while n <= x:
        if x % n == 0:
            return n
        n += 1

另外为了优化它，你只需要运行 while循环直到一个数的平方根找到它的质数因子，否则这个数本身就是质数因子。所以这是上面代码的优化版本：

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    while n*n <= x:
        if x % n == 0:
            return n
        n += 1
    return x

Answer 2

你进入了一个无限循环，因为如果不满足 return 条件，你不会更改 n 的值，如你所见 return 条件得到满足仅当您的数字 x 是 2 的倍数时，您才需要更改：

if x % n == 0:
    x += 1

与：

while n <= x:
    if x % n == 0:
        return x
    n += 1

要优化您的代码，您可以搜索素数 n 以除以小于 int(math.sqrt(x) + 1):

的 x

import math

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    max_n = int(math.sqrt(x) + 1)
    while n < max_n:
        if x % n == 0:
            return n
        n += 1

    return x

更好的是，您可以使用 Sieve of Eratosthenes 快速生成素数并针对您的 x:

进行测试

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes(y):
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while q < y:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]


def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one

    return next((i for i in gen_primes(int(math.sqrt(x) + 1)) if x % i == 0), x)

Returns 是 x 的约数的最小质数

Returns the smallest prime number that is a divisor of x

python

function

prime-factoring

python-3.x