首页 / 算法 / 试题 算法训练 最大质因数
试题 算法训练 最大质因数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了试题 算法训练 最大质因数,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1839字,纯文字阅读大概需要3分钟。
内容图文
![试题 算法训练 最大质因数](/upload/InfoBanner/zyjiaocheng/609/367956fc3f5741e4bda6e43f4fe10500.jpg)
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
给出N个数字,求出有最大的最大质因数的那个数
输入格式
第一行:一个整数N。
接下来的N行,每行一个整数A_i,表示给出的那N个数字。输出格式
第一行:一个整数,拥有最大的最大质因数的那个数。
样例输入
4
36
38
40
42
样例输出
38
数据规模和约定
60%的数据满足:N<=100
100%的数据满足:N<=2500,A_i<=20000
前言:
该题目是BASIC-16分解质因数的提高,有异曲同工之妙,方法还是对容器的使用,容器使用得当,可以大大提高时间效率,用起来比较方便。对分解质因数不了解的可以去本人上篇博文:试题 基础练习 分解质因数,网址:https://blog.csdn.net/weixin_49243150/article/details/113098201
解题方法:
- 在分解质因数的基础上,已经获得了N的质因数,并存入了容器,只需要在声明一个容器,用来存储每个N的最大质因数。
- 由于该容器有自动排序的功能(默认升序),然后就可以找到最大的质因数,然后找到对应的N即可
源代码:
#include<iostream>
#include<math.h>
#include<set>
using namespace std;
set<int>m;//找到N的质因数
multiset<int>q;//存储每一个N的最大的质因数
void find(int n)// 依旧是那个find()函数,只是改成set,可以去重复值,不变其实也可以。It's up to you
{
int flag = 0;
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
flag = 1;
m.insert(i);
if (n / i != i)
{
find(n / i);
break;//!!!
}
if (n / i == i)
{
m.insert(i);
}
}
}
if (flag == 0)
m.insert(n);
}
void Fmax(int n)//找最大的质因数。
{
int flag;
int a[2500];
int dp[2500];
for (int i = 0; i < n; i++)//输入N个数
{
cin >> a[i];
find(a[i]);//对应每个N的质因数
set<int>::iterator p = m.end();//声明直接指向最后一个元素的迭代器
q.insert(*(--p));//注意要是*(--p)对应着最后一个元素
dp[i] = *(p);//把某数N的最大质因数存入数组dp中
m.clear();
}
multiset<int>::iterator p = q.end();
int x = *(--p);//此时x的值为所有数据中的最大的质因数
for (int i = 0; i < n; i++)
{
if (dp[i] == x)
{
flag = i;
break;
}
}
cout << a[flag] << endl;//输出对应的N
}
int main()
{
int n;
cin >> n;
Fmax(n);
}
运行结果:
评测结果:
内容总结
以上是互联网集市为您收集整理的试题 算法训练 最大质因数全部内容,希望文章能够帮你解决试题 算法训练 最大质因数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。