0. 题目含义： 求解 n! 包含多少个因子a

1. 主要函数：

  • void getPrime()：筛法求素数的模板代码
  • int getBiggestPrimeFactor(int a)：获取输入a分解的最大的质因数
  • int getFactorNum(int n, int factor)：核心函数，递归求解，计算n!中包含质因子factor的数量

2. 理论依据：

任何大于2的正整数都可以写成若干质数乘积的形式。

n! 可以分解质因子乘积的形式，a也可以分解成若干质因子乘积的形式。而 n! 中包含多少个因子a，就可以转化为 n! 的质因子乘积包含多少a的质因子乘积。

而a分解出的最大质因子 biggestPrimeFactor 在 n! 质因子乘积中出现次数最少，因此 n! 包含因子a的数量就等于包含多少 biggestPrimeFactor 的数量。如果 biggestPrimeFactor 的指数 index 大于1，经过getFactorNum()求得的结果还需要除以 index 才是最终结果。

（有时间补个示意图，只有文字有点抽象。）

3. 代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

const int MAXN = 1001;

vector<int> prime;
bool isPrime[MAXN];

// 筛法求素数集合
void getPrime(){
    memset(isPrime, true, sizeof(isPrime));    // 元素全部初始化为true
    isPrime[0] = false, isPrime[1] = false;
    for(int i=2; i<MAXN; i++){
        if(!isPrime[i]){    // 非质数则跳过
            continue;
        }else{
            prime.push_back(i);
            for(int j=i*i; j<MAXN; j+=i){
                isPrime[j] = false;    //质数的倍数为非质数
            }
        }
    }
}

// 获取输入a分解的最大的质因数及其指数
pair<int ,int> getBiggestPrimeFactor(int a){
    int upper_bound = sqrt(a)+1;
    pair<int ,int> biggestPrimeFactor = make_pair(1, 0);
    for(int i=0;i<a && i<upper_bound;i++){
        int factor = prime[i];
        int index = 0;
        while(a%factor==0){    // 不断试除
            a/=factor;
            index++;
        }
        if(a==1){        // a最终被完全分解，所有质因数都已经找到
            biggestPrimeFactor.first = factor;
            biggestPrimeFactor.second = index;
            break;
        }
    }
    if(a>1){    // a最终没有被完全分解，那么a原来只含这一个大于sqrt(a)的质因数，且指数必定为1
        biggestPrimeFactor.first = a;
        biggestPrimeFactor.second = 1;
    }    
    return biggestPrimeFactor;
}


//核心函数：递归求解，计算 n! 中包含质因子 factor 的数量
int getFactorNum(int n, int factor){
        return n==0? 0 : n/factor + getFactorNum(n/factor,factor);
}

int main(){
    getPrime();
    int n, a;
    cin >> n >> a;
    // 设置pair保存：最大质因数的底数和指数
    pair<int ,int> biggestPrimeFactor = getBiggestPrimeFactor(a);
    int factor = biggestPrimeFactor.first;
    int res = getFactorNum(n, factor);
    // 得到的结果要除以最大质因数的指数才是最终结果
    res /= biggestPrimeFactor.second;
    cout << res << endl;
    return 0;
}