Problem 3: Largest Factor (100pts)

Problem

Write a function that takes an integer \(x\) that is greater than \(1\) and returns the largest integer that is smaller than \(x\) and evenly divides \(x\).

编写一个函数，接受一个大于 \(1\) 的整数 \(x\) 作为参数，并返回那个小于 \(x\) 且能整除 \(x\) 的最大整数。

def largest_factor(x):
    """Return the largest factor of x that is smaller than x.

    >>> largest_factor(15) # factors are 1, 3, 5
    5
    >>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
    40
    >>> largest_factor(13) # factor is 1 since 13 is prime
    1
    """
    "*** YOUR CODE HERE ***"

Hints

Hint1: To check if \(b\) evenly divides \(a\), you can use the expression a % b == 0, which can be read as, "the remainder of dividing \(a\) by \(b\) is \(0\)."

Hint2: You may want to review what is iteration?

• 要检查 \(b\) 是否能整除 \(a\)，您可以使用表达式 a % b == 0，这可以理解为：“\(a\) 除以 \(b\) 的余数是否为 \(0\)。”

• 您可能需要回顾一下什么是迭代？

• 当 x 为质数时，应输出 1

Solutions

使用 for 循环。这个问题可以进行简化，先计算不为1的最小因数，然后用 x 除以这个因数，就能得到结果。

当 x 为质数时，该循环会进行到 i = x，进而返回 1。也可以用特判解决这个问题。

def largest_factor(x):

    # Find the smallest factor except 1 first.
    for i in range(2, x + 1):
        if x % i == 0:
            # Then return its largest factor using //
            return x // i

---

使用 while 循环也可以完成相同任务。为了处理质数，选择当 i > x 时退出循环。

def largest_factor(x):
    i = 2
    # Find the smallest factor except 1 first.
    while i <= x:
        if x % i == 0:
            # Then return its largest factor using //
            return x // i

        i = i + 1

---

\(O(\sqrt{n})\) 复杂度的解法：考虑到若 \(x\) 为合数，则 \(x\) 的最小质因数小于等于 \(\sqrt{x}\)

def largest_factor(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return x // i
        i += 1
    return 1