上个月去北爱游玩, 看朋友圈传这个, 一直拖延至今天才有点时间写写题解:
后来了解到, 这个是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/
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK