题解 | #整除问题#

#include <iostream>
#include <vector>
#include<algorithm>
#include<cmath>
using namespace std;

int counta(int x,int a){
    int ans=0;
    while(x%a==0){
        ans++;
        x/=a;
    }
    return ans;
}

vector<int>prime;

void preprocess(){
    for(int i=0;i<=1000;i++){
        prime.push_back(1);
    }
    for(int i=2;i<=1000;i++){
        if(prime[i]==0)continue;
        for(int j=2;i*j<=1000;j++){
            prime[i*j]=0;
        }
    }
}
struct zhiyinshu{
    int factor;
    int num_a;
    int num_n_a;
};

int compare(zhiyinshu x,zhiyinshu y){
    return x.num_n_a<y.num_n_a;
}

int main(){
    vector<zhiyinshu>v;
    preprocess();
    int n,a;
    cin>>n>>a;
    for(int i=2;i<=a;i++){
        if(prime[i]==1&&a%i==0){//i是质数而且是a的因数,则统计a中的数量
            int num_a=0;
            while(a%i==0){
                num_a++;
                a/=i;
            }
            zhiyinshu z;z.factor=i;z.num_a=num_a;
            //统计n中i的数量
            int num_n=0;
            for(int j=2;j<=n;j++){
                num_n+=counta(j,i);
            }
            z.num_n_a=num_n/num_a;
            v.push_back(z);
        }
    }
    /*
    zhiyinshu lis[v.size()];
    for(int i=0;i<v.size();i++){
        lis[i]=zhiyinshu[i];
    }
    sort(lis,lis+v.size(),compare);

    */
    int output=100000;
    for(int i=0;i<v.size();i++){
        if (v[i].num_n_a<output)output=v[i].num_n_a;
    }
    cout<<output<<endl;
    return 0;
}