A24177. 最大质因子序列
填空题
中等
知识点
题目描述
最大质因子序列
题目描述
任意输入两个正整数m,n(1<m<n≤5000)，依次输出m到n之间每个数的最大质因子(包括m和n；如果某个数本身是质数，则输出这个数自身)。
输入
一行，包含两个正整数m和n，其间以单个空格间隔。
输出
一行，每个整数的最大质因子，以逗号间隔。
输入样例
5 10输出样例
5,3,7,2,3,5参考答案
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)//判断大于等于2的整数n是否是质数
{
for(int i = 2; i*i <= n; ++i)
if(n%i == 0)
return false;
return true;
}
int maxPrimeFactor(int n)//求n的最大质因子
{
for(int i = n; i >= 2; --i)//从大到小遍历
if(n%i == 0 && isPrime(i))
return i;
}
int main()
{
int m, n;
cin >> m >> n;
bool isFirst = true;//标志位：是否是第一个输出的数字
for(int i = m; i <= n; ++i)
{
if(isFirst)
isFirst = false;
else
cout<<',';
cout << maxPrimeFactor(i);
}
return 0;
}答案解析
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)//判断n是否是质数
{
if(n < 2)
return false;
for(int i = 2; i*i <= n; ++i)
if(n%i == 0)
return false;
return true;
}
int maxPrimeFactor(int n)//求n的最大质因子
{
int mx;
for(int i = 1; i*i <= n; ++i)//从小到大遍历
{
if(n%i == 0)
{
if(isPrime(n/i))
{
mx = n/i;
break;
}
else if(isPrime(i))
mx = i;
}
}
return mx;
}
int main()
{
int m, n;
cin >> m >> n;
bool isFirst = true;//标志位：是否是第一个输出的数字
for(int i = m; i <= n; ++i)
{
if(isFirst)
isFirst = false;
else
cout << ',';
cout << maxPrimeFactor(i);
}
return 0;
}
上一题
下一题