A27739. 质因数国豪知道素数的多种判定方法，比如枚举该数的所有因数，再比如可以用埃氏筛和欧拉筛进行优化。国庆想考验下国豪对于素数的理解和应用能力。于是，他提了一个问题：给定一个合数 c，请国豪统计这个合数 c 的质因数个数、每个质因数及其出现的次数。输入共一行，一个正整数 c。输出若干行。第一行表示 c 的质因数的个数。接下来若干行，按照字典序给出 c 的每个质因数及其出现的次数。样例输入600样例输出3…
填空题
中等
知识点
题目描述
质因数
国豪知道素数的多种判定方法，比如枚举该数的所有因数，再比如可以用埃氏筛和欧拉筛进行优化。国庆想考验下国豪对于素数的理解和应用能力。于是，他提了一个问题：给定一个合数 c，请国豪统计这个合数 c 的质因数个数、每个质因数及其出现的次数。
输入
共一行，一个正整数 c。
输出
若干行。第一行表示 c 的质因数的个数。接下来若干行，按照字典序给出 c 的每个质因数及其出现的次数。
样例输入
600
样例输出
3
2 3
3 1
5 2
说明
600=2^ 3 *3*5^ 2 ，600 有三个质因数，从小到大依次是 2,3,5，其中 2 出现了 3 次，3 出现了 1 次,5 出现了 2 次。
数据范围
4<=c<=2000000000
参考答案
#include<bits/stdc++.h>
using namespace std;
int n,k,a[101];
int main()
{
int sum=0;
cin>>n;
for(int i=2;i<=n;i++)
{
while(n%i==0)
{
k++;
a[k]=i;
n/=i;
}
}
for(int i=1;i<=k-1;i++)
{
if(a[i]!=a[i+1])
sum++;
}
cout<<sum+1<<endl;
int c=1;
for(int i=1;i<=k;i++)
{
if(a[i]==a[i+1])
c++;
else
{
cout<<a[i]<<" "<<c<<endl;
c=1;
}
}
return 0;
}
上一题
下一题