定义
对于任何正整数x，其约数的个数记作g(x)。
e.g. g(1)=1、g(6)=4。
如果某个正整数x满足：g(x) > g(i) (0 < i < x)，则称x为反质数。————摘选自《百度百科》
性质
- 一个反素数的质因子必然是从2开始连续的质数。
- p=2^t1*3^t2*5^t3*7^t4……必然t1≧t2≧t3≧t4≧……
证明
（p为约数个数一定的最小正整数）
1.
设p1=2^t1*3^t2*5^t3*7^t4…..
假设质因子从x开始（x为质数&&x!=2）
则p2=2^t1’*x2^t2’*x3^t3’*x4^t4’……
∵2为最小质数
∴x > 2
∵g(p1)=g(p2)
∴t1=t1’,t2=t2’……
∴2^t1 < 2^t1’……
∴2^t1*3^t2*5^t3*7^t4…… < 2^t1’*x2^t2’*x3^t3’*x4^t4’……
∴p1 < p2
∴p1为约数个数一定的最小正整数
∴得证
2.
设p=2^t1*3^t2*5^t3*7^t4……
∵2 < 3 < 5 < 7<……
∴2^k < 3^k < 5^k < 7^k……
又∵p为约数个数一定的最小正整数
∴k一定时x^k，x越小越好
∵g(p)为一定
∴t……为一定
又∵2 < 3 < 5< 7……k一定时x^k，x越小越好，p=2^t1*3^t2*5^t3*7^t4……
∴t1≧t2≧t3≧t4≧……
∴得证
例题
（在题目中实际用途）
Number With The Given Amount Of Divisors
———————CodeForces - 27E———————题目链接
题目
Given the number n, find the smallest positive integer which has exactly n divisors. It is guaranteed that for the given n the answer will not exceed 10^18.
Input
The first line of the input contains integer n (1?≤?n?≤?1000).
Output
Output the smallest positive integer with exactly n divisors.
Examples
Input
4
Output
6
Input
6
Output
12
题意
给定一个正整数n，求一个最小的正整数，使得它的因子个数恰为n (1?≤?n?≤?1000)。保证答案不超过10^18。
也就是g(x)=n,求x。
思路
- 用搜索沿因子个数和质数从小到大搜，找到，更新
- 通过性质来剪枝，提高效率
反素数深度分析（帮助理解搜索思路）
比如p=2^t1*3^t2*5^t3*7^t4……，以每一个质因子为树的一层搜索，深度为g(p).
实现代码
#include<cstdio>
int n;
int p[12]={
2,3,5,7,11,13,17,19,23,29};
long long ans=1e18;
void dfs(int d,long long x,int id)//注意答案数据范围
{if(d>n)return;if(d==n){if(ans>x)ans=x;return;}for(int i=1;i<=64;i++){if(ans<x*p[id])break;dfs(d*(i+1),x*=p[id],id+1);}
}
int main()
{scanf("%d",&n);dfs(1,1,0);printf("%lld",ans);
}