做题送美人 Python 题解: (两质数相乘等于 707829217)

上个月去北爱游玩, 看朋友圈传这个, 一直拖延至今天才有点时间写写题解:

两质数相乘等于 707829217

后来了解到, 这个是HR的套路, 并不是真的做题送美人, 不过这题还是挺有意思的, 至少能复习一下素数的一些相关算法.

暴力穷举

题目要求是两质数相乘 等于 707829217, 这数也不大, 至少不需要用于大整数 bignum, 2的31次方是: 2147483648. 因此我们可以从3开始暴力, 每次加2, 直到 根号(707829217)=26605即可, 这数很小, 现在的计算机秒秒就出结果了.

算到根号就可以了, 因为暴力小的数, 大的数自然可以用707829217一除即可. 然后我们分别判断一下是否是质数即可.

质数判断从2到 根号, 每次加2, 然后判断是否有合数. 这一判断时间复杂度是 O(Sqrt(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from math import sqrt
 
total = 707829217
sqrt_total = int(sqrt(total))
 
def isPrim(N): # 判断是否是质数, 复杂度 O(sqrt(N))
    for i in range(2, int(sqrt(N)), 2):
        if total % i == 0:
            return False;
    return True
 
for i in range(3, sqrt_total, 2):
    if total % i == 0:         # 必须能除得尽
        another = total // i   # 大的质数 
        if (isPrim(another) and isPrim(i)): 
            print(another, "*", i, "=", another*i)
            break

from math import sqrt

total = 707829217
sqrt_total = int(sqrt(total))

def isPrim(N): # 判断是否是质数, 复杂度 O(sqrt(N))
    for i in range(2, int(sqrt(N)), 2):
        if total % i == 0:
            return False;
    return True

for i in range(3, sqrt_total, 2):
    if total % i == 0:         # 必须能除得尽
        another = total // i   # 大的质数 
        if (isPrim(another) and isPrim(i)): 
            print(another, "*", i, "=", another*i)
            break

空间复杂度是常数O(1), 时间复杂度大循环 O(Sqrt(N)), 加上测试素数的, 大概是 O(Sqrt(N)Sqrt(N)) – 也就是O(N). 我们这里说复杂度是假设题目给定的这个数 707829217 可以改变的话.

程序很快就给出了: 86627 * 8171 = 707829217

埃拉托斯特尼筛法 Sieve of Eratosthenes

我们可以预先处理好这个素数检查函数, 可以用埃拉托斯特尼筛法来预先准备好素数表, 简单来说就是从2开始, 然后把4, 6, 8, 10 .. 划掉, 然后到3了, 把9, 12, 15… 划掉, 剩下的数就是素数.

但是这个预处理也需要时间的, 而且准备这个表也需要额外空间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

prims = [True] * total
 
for i in range(3, sqrt_total, 2):
    if prims[i]:
        j = i * i
        while j < total:
            prims[j] = False # 划掉倍数
            j += i
 
for i in range(3, sqrt_total, 2):
    if total % i == 0:
        another = total // i
        if (prims[another] and prims[i]):
            print(another, "*", i, "=", another*i)
            break

prims = [True] * total

for i in range(3, sqrt_total, 2):
    if prims[i]:
        j = i * i
        while j < total:
            prims[j] = False # 划掉倍数
            j += i

for i in range(3, sqrt_total, 2):
    if total % i == 0:
        another = total // i
        if (prims[another] and prims[i]):
            print(another, "*", i, "=", another*i)
            break

检查素数的时间复杂度是查表 O(1) 但是准备这个表却需要 O(nloglogn) 并且需要 O(N) 额外的空间复杂度. 所以整个算法比第一个还慢, 但是耐心等, 还是会出结果的.

费马小定理 快速素数判定算法

其实, 关键就在这个检查素数的算法, 如果我们能提速, 那么整个速度就会加快. 费马小定理可以用来快速的检测素数, 也就是如果 p 是素数, 那么 任意的整数 a, 有 a^(p-1)除于余数为1. 如果不为1, 那么一定不是质数. 如果为1, 也不一定是质数. 但是如果我们连续多数的选择随机数a, 测试都是1的话, 那么质数的概率就大大增加.

所以我们可以连续的测试k次来提高测试的准确度, k=10就已经可以得到很好的效果了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def probalPrime(n, s):
    if n <= 1:
        return False
    if n <= 3:
        return True
    for _ in range(s):
        a = randint(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    return True
                       
for i in range(3, sqrt_total, 2):
    if total % i == 0:
        another = total // i
        if probalPrime(another, 10) and probalPrime(i, 10):
            print(another, "*", i, "=", another*i)
            break             

def probalPrime(n, s):
    if n <= 1:
        return False
    if n <= 3:
        return True
    for _ in range(s):
        a = randint(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    return True
                       
for i in range(3, sqrt_total, 2):
    if total % i == 0:
        another = total // i
        if probalPrime(another, 10) and probalPrime(i, 10):
            print(another, "*", i, "=", another*i)
            break             

pow 函数的复杂度是 O(logN), 而大循环是 O(Sqrt(N)), 所以整体复杂度是 O(K.log(N).Sqrt(N)). 这里的K是测试素数的次数, 一般就是K=10, 所以是常数, 可以忽略.

pow 函数 O(logN) 的递归示例如下(实际应用需要换成迭代, 否则对于大的输入数据 会栈溢出 stack over flow):

1
2
3
4
5
6
7
8

def powmod(a, b, n):
    if b == 1:
        return a % n
    r = powmod(a, b / 2, n)
    r = r * r % n
    if (b & 1) == 1: # 奇数
        r = r * a % n
    return r

def powmod(a, b, n):
    if b == 1:
        return a % n
    r = powmod(a, b / 2, n)
    r = r * r % n
    if (b & 1) == 1: # 奇数
        r = r * a % n
    return r

Linux 下的 factor 工具

LINUX下有一个 factor 工具, 可以给出一个正整数的质数(因素)分解.

1
2

# factor 707829217
707829217: 8171 86627

# factor 707829217
707829217: 8171 86627

FACTOR(1)                                                                         User Commands                                                                        FACTOR(1)

NAME
       factor - factor numbers

SYNOPSIS
       factor [NUMBER]...
       factor OPTION

DESCRIPTION
       Print the prime factors of each specified integer NUMBER.  If none are specified on the command line, read them from standard input.

       --help display this help and exit

       --version
              output version information and exit

AUTHOR
       Written by Paul Rubin, Torbjorn Granlund, and Niels Moller.

REPORTING BUGS
       GNU coreutils online help: <http: //www.gnu.org/software/coreutils></http:>
       Report factor translation bugs to <http: //translationproject.org/team></http:>

COPYRIGHT
       Copyright 2017 Free Software Foundation, Inc.  License GPLv3+: GNU GPL version 3 or later <http: //gnu.org/licenses/gpl.html>.
       This is free software: you are free to change and redistribute it.  There is NO WARRANTY, to the extent permitted by law.

SEE ALSO
       Full documentation at: </http:><http: //www.gnu.org/software/coreutils/factor>
       or available locally via: info '(coreutils) factor invocation'

GNU coreutils 8.28                                                                January 2018                                                                         FACTOR(1)
</http:>

正整数因式分解在线工具和API

做了一个简单的在线工具: 正整数因式分解在线工具

还有另一个附加题, 敬请关注更新.

References:

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
https://helloacm.com/fermat-prime-test-algorithm/