一个数等于两个不同素数的乘机_【朝夕的ACM笔记】数论-反素数
【朝夕的ACM笔记】目录与索引
反素数
一、基础概念
反素数(Anti-prime number)是这样的一类数：
对于正整数
例如，前四个反素数是1,2,4,6。
以6来说明，6的因子个数为4(1,2,3,6)，比任何一个小于6的正整数因子个数都要多。
反素数有两个重要的性质：
①反素数
我们知道，任何一个正整数都可以表示为若干素数的幂的乘积（其中素数就是其他素数的0次幂与该素数的1次幂的乘积，合数则可以通过分解质因数来得到），所以该性质前半部分很好理解。
后半部分则需要另一个重要定理：
对于正整数
这本质上就是在进行质因数的排列组合，若一个质因数
而反素数要求我们使数字的因子个数尽量多，本身数值尽量小。
则根据上述定理，在因子个数固定的情况下，小的素数的次数必然更大，否则必存在数值更小且因子个数相同的另一个正整数。
举例来说：若
②反素数的质因子必然是从2开始的连续素数。
由第①性质即可证，若存在一质因子
二、求解反素数
一般的求解反素数题目都是让求一定范围内的最大反素数，其代码算法使用的主要是反素数的两个性质。
我们只需要通过DFS来枚举每个质因数的次数，并保证其单调不增，在过程中不断更新答案即可。
值得一提的是，对于
参考代码：
#include