贝壳-算法笔试题

贝壳，笔试第一题 感觉挺有意思。。通过了 （其实是第二题不想写，第三题不会）

1. 工资纳税金额 为 工资 的 最大因数（除自身外），工资可以拆为 任意份 (每份值必须 >1)，每份单独纳税

input ： 工资 x (1 < x < 10^9)

output ：最少纳税值

解题关键是：质数 的 税是 1 ，所以 合数 拆为 质数之和；

又因 哥德巴赫猜想：任何大于5的奇数都是三个素数之和 （奇合数 纳税 最多为 3）；

欧拉回信：每个大于2的偶数,都可表示为 两个质数之和 （故 偶数 纳税 为 2）

def isPrime(n):
    i = 2
    while i <= n ** 0.5:
        if n % i == 0:
            return False
        i += 1
    return True
def f(x):
    if isPrime(x):
        return 1
    if x % 2 == 0:
        return 2
    i = x - 1
    res = 0
    while i >= 2:
        if isPrime(i):
            res += 1
            x -= i
            i = x
            continue
        i -= 1
    return res

奇合数 纳税 最多为 3，为 2 时 一定是 拆为 2 和 x - 2，因为 奇 + 奇 = 偶，故需要有一个偶质数 即2
因此 函数 可简化为...

def f(x):
    if isPrime(x):
        return 1
    if x % 2 == 0 or isPrime(x-2):
        return 2
    return 3