文章
60
粉丝
361
获赞
43
访问
522.9k
思路:
1、对N!分解质因数,所以分别对1、2、3……N分解质因数,然后用一个数组下标记录该质因数的个数
2、对a分解质因数,然后计算相同质因数下,1步质因数个数除以2步质因数个数的最小值即为所求
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int prime[2][maxn];
void getPrime() {
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= maxn; i++) //输入数
{
if (!prime[0][i]) //未被动过,每个数赋值i prime[0]存的是素数的个数
prime[0][++prime[0][0]] = i;
for (int j = 1; j <= prime[0][0] && prime[0][j] * i <= maxn; j++)
{
prime[0][prime[0][j] * i] = 1;//素数倍数不是素数
if (i % prime[0][j] == 0) break;
}
}
}
int main()
{
int n,a;
int b[1000]={0};
while(cin>>n>>a)
{
getPrime();//做出N内的质因数
for(int k=2;k<=n;k++)//N个数
{
int num=k;
//对每个数分解质因数
for(int i=1;i<=prime[0][0];i++)
{
while(num%prime[0][i]==0)
{
num=num/prime[0][i];
prime[1][i]++;//记录质因数个数
}
}
}
//对a分解质因数
for(int i=1;i<=prime[0][0];i++)
{
while(a%pr...
登录后发布评论
暂无评论,来抢沙发