没错就是这张套路图，据说是 segment fault 的招聘？无聊刷一下题，抛砖引玉。（知乎那边也回了贴，话说破乎的编辑器还真不适合贴代码……）

正好最近在出招聘测试的笔试题，在网上看到跟第 1 题类似的，数字比这个大 10 倍有多。自己做了一下发现如果之前没刷过类似的，要在限时内在纸上写出优化过的代码并不容易，就放弃把它收进题库了……

现成的贴上来：

import time
import math


def is_prime(x):
    if x <= 1:
        return False

    if x == 2:
        return True

    for i in range(3, int(math.sqrt(x)) + 1, 2):
        if x % i == 0:
            return False

    return True


def prime_factorization(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0 and is_prime(i):
            quotient = x // i

            if is_prime(quotient):
                print(i, quotient)


if __name__ == '__main__':
    t1 = time.time()
    prime_factorization(707829217)
    t2 = time.time()

    print(f'ms: {t2 * 1000 - t1 * 1000}')

输出：

8171 86627
ms: 3.166015625

我能想到的优化点有 3 个：

• 1、n 的最小质因数（能整除给定正整数的质数）<= √n（因为如果 √n 是整数，n 一定是合数）。因此没必要循环到 n，√n + 1 就够了。
  • 优化后时间复杂度从 O(n) 降到 O(log(n)) 。
  • 我找到的题里的数字是 7140229933，开根号后约 84500，少循环了 7140145433 次！本来要跑几分钟，优化后 230ms 左右出结果。
• 2、解一定是整数，如果不能整除某个数 a，也就没必要判断 a 是不是质数了。
  • 调整判断条件的次序，优化后 14ms 左右出结果。
• 3、除了 2，其他质数都是奇数，循环时可以跳过偶数，减少一半判断。
  • 本来对于判断是否质数来说这个优化点很重要，但在这里贡献几乎忽略不计，做了第二点优化之后已经没剩几次需要判断的了。

第二题：

没有用典型的 DP 模板（因为我想了半天都套不上……），题目条件太简单，用了取巧的办法硬是磨出来了，目测反而会比 DFS 快不少。

def get_answer(n):
    """
    这题有个取巧的方法，十位以上是 3 的时候，奇数的个数是 10^i / 2。例如 300-400 之间有 10^2 / 2 = 50 个奇数，如此类推。
    用记忆化搜索的思路把结果缓存起来，然后注意一下最后每位数字的限制，就能直接推出最终结果。

    速度极快，哪怕是 333333333333333333333333333333333333333 这种大数字也就 1ms 左右。

    题中 866278171 这个数字其实不是好例子，因为所有位都不是 3。
    下面注释那几处地方假如没注意，就连 N = 3 都出 bug 的情况下这个数也能得到正确结果……

    测试：1 3 4 9 10 13 29 31 33 39 41 43 100 299 301 303 333 399 400 1000
        1224 1234 1244 10000 33333 1234567 12345678
    """
    count = 0
    nums = []
    results = []

    x = n
    while x > 0:
        # nums 存储 N 的各位数字，个位在前，最高位在最后
        nums.append(x % 10)
        # results 是二维数组，行数为 N 的位数，11 列分别代表 0-9 开头的数字 和总计
        # 把每一位各数字开头的 3 的总数存起来
        results.append([0] * 11)
        x //= 10

    digits = len(nums)

    # 个位特殊处理
    results[0][3] = 1
    results[0][-1] = 1
    if nums[0] >= 3:  # 注意这里
        count += 1

    for i in range(1, digits):
        for j in range(9 + 1):
            results[i][j] += results[i - 1][-1]

            if j == 3:
                results[i][j] += 10 ** i // 2

            results[i][-1] += results[i][j]

            # 注意加的时候只能小于 N 在这一位的数字，否则会超出。
            # 如果这一位为 0 就跳过（在下一位或下几位会包含进去）。
            if j < nums[i]:
                count += results[i][j]

        # 补上 N 十位以上为 3 开头时漏统计的情况（因为不能读缓存）
        if nums[i] == 3:
            count += (sum(nums[j] * 10 ** j for j in range(i)) + 1) // 2

    return count

输出：（没错就是这么快）

441684627
ms: 0.07421875

上面的方法不太好验证正确性，可以配合穷举和 1234567 之类较小的数字做测试：

def brute_force(n):
    """
    如果是现场做笔试题，想不出 DP 至少写上这个凑数……
    效率很低，算个 12345678 都要 7 秒左右，据说算完题中的数要 7-10 分钟。
    """
    count = 0

    i = 1
    while i <= n:
        x = i
        while x > 0:
            if x % 10 == 3:
                count += 1
            x //= 10

        i += 2

    return count