素数
素数与合数的定义,见 数论基础。
素数计数函数:小于或等于
素数判定
我们自然地会想到,如何用计算机来判断一个数是不是素数呢?
实现
暴力做法自然可以枚举从小到大的每个数看是否能整除
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 |
|
这样做是十分稳妥了,但是真的有必要每个数都去判断吗?
很容易发现这样一个事实:如果
这个结论告诉我们,对于每一对
由于
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 |
|
素性测试
定义
素性测试(Primality test)是一类在 不对给定数字进行素数分解(prime factorization)的情况下,测试其是否为素数的算法。
素性测试有两种:
- 确定性测试:绝对确定一个数是否为素数。常见示例包括 Lucas–Lehmer 测试和椭圆曲线素性证明。
- 概率性测试:通常比确定性测试快很多,但有可能(尽管概率很小)错误地将 合数 识别为质数(尽管反之则不会)。因此,通过概率素性测试的数字被称为 可能素数,直到它们的素数可以被确定性地证明。而通过测试但实际上是合数的数字则被称为 伪素数。有许多特定类型的伪素数,最常见的是费马伪素数,它们是满足费马小定理的合数。概率性测试的常见示例包括 Miller–Rabin 测试。
接下来我们将着重介绍几个概率性素性测试:
Fermat 素性测试
Fermat 素性检验 是最简单的概率性素性检验。
我们可以根据 费马小定理 得出一种检验素数的思路:
基本思想是不断地选取在
实现
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 |
|
如果
很遗憾,费马小定理的逆定理并不成立,换言之,满足了
Carmichael 函数
对正整数
恒成立的最小正整数
即:
Carmichael 函数有如下性质:
(Carmichael 定理)对任意素数
和任意正整数 ,进而有:
对任意正整数
,有对任意正整数
, ,有
令
的唯一分解式为 ,则由 中国剩余定理 和 Carmichael 定理易证。
进而有:
- 对任意正整数
, ,有
- 对任意正整数
Carmichael 数
对于合数
比如
我们可以用如下方法判断合数
Korselt 判别法1
合数
上述判别法可简化为:
Note
合数
Carmichael 数有如下性质:
- Carmichael 数无平方因子且至少有
个不同的质因子。 设
为小于 的 Carmichael 数个数,则:
注意
「若
如
注意到
而
Miller–Rabin 素性测试
Miller–Rabin 素性测试(Miller–Rabin primality test)是进阶的素数判定方法。它是由 Miller 和 Rabin 二人根据费马小定理的逆定理(费马测试)优化得到的。因为和许多类似算法一样,它是使用伪素数的概率性测试,我们必须使用慢得多的确定性算法来保证素性。然而,实际上没有已知的数字通过了高级概率性测试(例如 Miller–Rabin)但实际上却是合数。因此我们可以放心使用。
在不考虑乘法的复杂度时,对数
二次探测定理
如果
要证明该定理,只需将上面的方程移项,再使用平方差公式,得到
实现
根据卡迈克尔数的性质,可知其一定不是
不妨将费马小定理和二次探测定理结合起来使用:
将
还有一些实现上的小细节:
- 对于一轮测试,如果某一时刻
,则之后的平方操作全都会得到 ,则可以直接通过本轮测试。 - 如果找出了一个非平凡平方根
,则之后的平方操作全都会得到 。可以选择直接返回false
,也可以放到 次平方操作后再返回false
。
这样得到了较正确的 Miller Rabin:(来自 fjzzq2002)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
另外,假设 广义 Riemann 猜想(generalized Riemann hypothesis, GRH)成立,则对数
而在 OI 范围内,通常都是对
也可以选取
注意如果要使用上面的数列中的数
- 所有的数都要取一遍,不能只选小于
的; - 把
换成 ; - 如果
或 ,则直接通过该轮测试。
反素数
引入
顾名思义,素数就是因子只有两个的数,那么反素数,就是因子最多的数(并且因子个数相同的时候值最小),所以反素数是相对于一个集合来说的。
一种符合直觉的反素数定义是:在一个正整数集合中,因子最多并且值最小的数,就是反素数。
定义
如果某个正整数
注意
注意区分 emirp,它表示的是逐位反转后是不同素数的素数(如 149 和 941 均为 emirp,101 不是 emirp)。
过程
那么,如何来求解反素数呢?
首先,既然要求因子数,首先要做的就是素因子分解。把
但是显然质因子分解的复杂度是很高的,并且前一个数的结果不能被后面利用。所以要换个方法。
我们来观察一下反素数的特点。
反素数肯定是从
开始的连续素数的幂次形式的乘积。数值小的素数的幂次大于等于数值大的素数,即
中,有
解释:
如果不是从
开始的连续素数,那么如果幂次不变,把素数变成数值更小的素数,那么此时因子个数不变,但是 的数值变小了。交换到从 开始的连续素数的时候 值最小。如果数值小的素数的幂次小于数值大的素数的幂,那么如果把这两个素数交换位置(幂次不变),那么所得的
因子数量不变,但是 的值变小。
另外还有两个问题,
对于给定的
,要枚举到哪一个素数呢?最极端的情况大不了就是
,所以只要连续素数连乘到刚好小于等于 就可以的呢。再大了,连全都一次幂,都用不了,当然就是用不到的啦!我们要枚举到多少次幂呢?
我们考虑一个极端情况,当我们最小的素数的某个幂次已经比所给的
(的最大值)大的话,那么展开成其他的形式,最大幂次一定小于这个幂次。unsigned long long
的最大值是 ,所以可以枚举到 。
细节有了,那么我们具体如何具体实现呢?
我们可以把当前走到每一个素数前面的时候列举成一棵树的根节点,然后一层层的去找。找到什么时候停止呢?
当前走到的数字已经大于我们想要的数字了
当前枚举的因子已经用不到了(和
重复了嘻嘻嘻)当前因子大于我们想要的因子了
当前因子正好是我们想要的因子(此时判断是否需要更新最小
)
然后 dfs 里面不断一层一层枚举次数继续往下迭代可以。
常见题型
- 求因子数一定的最小数
例题 Codeforces 27E. A number with a given number of divisors
求具有给定除数的最小自然数。请确保答案不超过
解题思路
对于这种题,我们只要以因子数为 dfs 的返回条件基准,不断更新找到的最小值就可以了
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
- 求 n 以内因子数最多的数
例题 ZOJ - More Divisors
大家都知道我们使用十进制记数法,即记数的基数是
解题思路
思路同上,只不过要改改 dfs 的返回条件。注意这样的题目的数据范围,32 位整数可能溢出。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|
参考资料与注释
- Rui-Juan Jing, Marc Moreno-Maza, Delaram Talaashrafi, "Complexity Estimates for Fourier-Motzkin Elimination", Journal of Functional Programming 16:2 (2006) pp 197-217.
- 数论部分第一节:素数与素性测试
- Miller-Rabin 与 Pollard-Rho 学习笔记 - Bill Yang's Blog
- Primality test - Wikipedia
- 桃子的算法笔记——反素数详解(acm/OI)
- The Rabin-Miller Primality Test
- Bach, Eric , "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55:191 (1990) pp 355–380.
- Deterministic variant of the Miller-Rabin primality test
- Fermat pseudoprime - Wikipedia
- Carmichael number - Wikipedia
- Carmichael function - Wikipedia
- Carmichael Number -- from Wolfram MathWorld
- Carmichael's Lambda Function | Brilliant Math & Science Wiki
Korselt, A. R. (1899). "Problème chinois".L'Intermédiaire des Mathématiciens.6: 142–143. ↩
W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers".Annals of Mathematics. 140 (3): 703–722. ↩
Erdős, P. (1956). "On pseudoprimes and Carmichael numbers".Publ. Math. Debrecen. 4 (3–4): 201–206. ↩
PINCH, Richard GE. The Carmichael numbers up to
. ↩
本页面最近更新:2024/10/15 00:03:08,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:iamtwz, Marcythm, StudyingFather, 383494, abc1763613206, Alpacabla, Backl1ght, CCXXXI, drkelo, Early0v0, Enter-tainer, Great-designer, greyqz, GuanghaoYe, H-J-Granger, HeRaNO, Ir1d, isdanni, kenlig, ksyx, lazyasn, MegaOwIer, Menci, ouuan, shawlleyw, shopee-jin, shuzhouliu, Siger Young, Tiphereth-A, TrisolarisHD, untitledunrevised, void-mian, Voileexperiments, weilycoder, Xeonacid, xtlsoft, YuzhenQin
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用