题解 | #整除问题# 分解质因数

// 思路：线性筛选质因数，即任意正整数（n,a>1）都可以被分解为有限个质数之积
// 如：12 = 2^2 * 3
// map可以用下标访问，而set不行
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
// 统计num中质因子的数量
void getAllFacs(unordered_map<int, int>& fac_n, int num) {
    for (int i = 2; i <= sqrt(num);i++) { // 上界有等号
        if (num <= 1) return;
        while (num % i == 0) { // num = faci^n * facj^m * ...?: 质因子分解方法
            fac_n[i]++;
            num /= i;
        }
    }
    if (num > 1) fac_n[num]++;
}
int main() {
    int n, a, k = INF;
    cin >> n >> a;
    unordered_map<int, int> fac_2toN, fac_a; // 散列表存储质因数
    getAllFacs(fac_a, a); // 对a分解质因数
    for (int i = 2; i <= n; i++) getAllFacs(fac_2toN, i); // 对2~n分解质因数
    for (int i = 2; i <= a; i++) { // 开始比较质因子次方 选出做小的作为 k
        if (fac_a[i] != 0) {
            if(fac_2toN[i]/fac_a[i] < k) k=fac_2toN[i]/fac_a[i];
        }
    }
    cout << k << endl;
    return 0;
}