算数基本定理即质因子分解定理，顾名思义，将一个数的所有质因子，及每个质因子的数量分解出来。（算数基本定理是数论的一个公理） 在代码的实现的时候不能直接暴力，太慢，一般配合欧拉筛，这里欧拉筛的作用不是素数打表，而是求所有小于N的自然数的最小质因子，及minp。及对任意一个x都让他除尽minp[x]，到x % minp[x] 不为0为止，之后再让新的x 除尽 新的minp[x]，x为1为止。 看道板子题 1295. X的因子链 输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。
输入格式 输入包含多组数据，每组数据占一行，包含一个正整数表示 X。
输出格式 对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。
每个结果占一行。
数据范围 1≤X≤220 输入样例： 2 3 4 10 100 输出样例： 1 1 1 1 2 1 2 2 4 6
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; const int N = (1 << 20) + 15; int x,p[N],minp[N],cnt,c[30][30],fact[30],sum[30]; bool book[N]; void oula() { for(int i = 2; i < N; i ++) { if(!book[i]) { p[cnt ++] = i; minp[i] = i; } for(int j = 0; j < cnt && i * p[j] < N; j ++) { int temp = i * p[j]; book[temp] = true; minp[temp] = p[j]; if(i % p[j] == 0) break; } } } int main() { oula(); // for(int i = 0; i < 30; i ++) { c[i][0] = 1; c[i][i] = 1; c[i][1] = i; } for(int i = 3; i < 30; i ++) { for(int j = 2; j < i; j ++) { c[i][j] = c[i-1][j-1] + c[i-1][j]; } } / while(scanf("%d",&x) != EOF) { int tot = 0,ans = 0,k = 0; memset(sum,0,sizeof sum); memset(fact,0,sizeof fact); while(x > 1) { int temp = minp[x]; fact[ans ++] = temp; while(x % temp == 0) { x /= temp; sum[k] ++; tot ++; } //printf("x = %d temp = %d sum = %d\n",x,temp,sum[tot]); k ++; } ll res = 1; int sniper = tot; for(int i = 0; i < tot; i ++) { //printf("c[%d][%d] = %d\n",sniper,sum[i],c[sniper][sum[i]]); res *= (ll)c[sniper][sum[i]]; sniper -= sum[i]; } printf("%d %lld\n",tot,res); } return 0; }