输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。
输入格式
输入包含多组数据，每组数据占一行，包含一个正整数表示 X。
输出格式
对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。
每个结果占一行。
数据范围
1≤X≤220
输入样例：
2
3
4
10
100
输出样例：
1 1
1 1
2 1
2 2
4 6
关于线性筛法
线性筛法是一种快速选出质数的算法
大致原理为 从2开始筛选素数 将每次筛选好的素数存储到primes 数组中然后将含有该素数因子的和数全部筛掉 用此算法的时间复杂度可以达到O(n);
下面是关于线性筛法的算法
int primes[N];//用于存放素数
int minp[N];//存最小质因子
int cnt; //记录素数的个数 也作为primes数组的下标使用
bool st[N];//记录当前的数是否有被筛过void get_primes(int n) //选出0-n中所有的素数
{
for(int i = 2; i <= n; i ++){
if(st[i] == false){
st[i] = true;minp[i] = i;primes[cnt ++] = i;}for(int j = 0; i * primes[j] <= n; j ++){
st[i * primes[j]] = true;//筛掉合数minp[i * primes[j]] = true;if(i % primes[j] == 0)break;}}
}
#include<iostream>using namespace std;typedef long long ll;const int N = (1 << 20) + 10;int primes[N];//存质数
int minp[N];//存最小质因子
int cnt;
bool st[N];
int sum[N];//质因子出现的次数void get_primes(int n)
{
for(int i = 2; i <= n; i ++){
if(!st[i]){
minp[i] = i;primes[cnt ++] = i;}for(int j = 0; primes[j] * i <= n; j ++){
int t = primes[j] * i;st[t] = true;//标记合数 minp[t] = primes[j];if(i % primes[j] == 0) break;如果i是前面某个素数的倍数时, 说明i以后会由某个更大的数乘这个小素数筛去//同理, 之后的筛数也是没有必要的, 因此在这个时候, 就可以跳出循环了}}
}int main()
{
get_primes(N);int x;while(scanf("%d", &x) != EOF){
int k = 0, tol = 0;//k表示第i个质因子的下标，tol用于记录最大长度while(x > 1){
int p = minp[x];sum[k] = 0;while(x % p == 0)//处理当前质因子，求其出现的次数 {
sum[k] ++;tol ++;x /= p;}k ++;} //求所有质因子出现总次数的全排列 ll res = 1;for(int i = 2; i <= tol; i ++){
res *= i; //tol!}//去除各个质因子重复出现的次数for(int i = 0; i < k; i ++){
for(int j = 1; j <= sum[i]; j ++){
res /= j;}}cout << tol << ' ' << res << endl; }
}