//素数筛选生成素数表,分解质因子,求质因子的最小幂
//求最大 k 使 m^k 是 n!的约束, 分解 m 的质因子,然后求质因子的最小幂。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
#define MAXN 10110
bool vis[MAXN];
int prime[MAXN],c;
void sieve(int n)
{
int m=(int)sqrt(n*1.0+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++) if(!vis[i])
for(int j=i*i;j<=n;j+=i) vis[j]=1;
}
int gen_primes(int n)
{
sieve(n);
c=0;
for(int i=2;i<=n;i++) if(!vis[i])
prime[c++]=i;
return c;
}
//统计因子的幂
int cnt(int p,int n)
{
int ans=0;
for(int i=p;i<=n;i*=p)
ans+=(n/i);
return ans;
}
int main()
{