题目3：找出一个合数的最大质数因子
本帖最后由 欧拉计划 于 2023-9-17 21:05 编辑题目3：找出一个合数的最大质数因子
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
题目翻译：
13195 的质数因子有 5, 7, 13 和 29。
那么请问 600851475143 的最大质数因子是多少？
视频讲解：
https://www.bilibili.com/video/BV1Mh4y1t7kB/
思路解析及源码参考（C & Python）：
**** Hidden Message *****
这个数据怎么这么熟悉{:10_256:}
#include <iostream>
#include <algorithm>
using namespace std;
long long n = 600851475143, ans;
int main() {
for (int i = 2; i * i <= n; ++i) {
while (n % i == 0) {
ans = max(ans, 1ll * i);
n /= i;
}
}
if (n > 1) {
ans = max(ans, n);
}
cout << ans << endl;
return 0;
}
输出 6857，如果还要进一步优化，可以使用欧拉筛。 讲得很详细，学到了{:10_275:}
首楼打卡 zhangjinxuan 发表于 2023-5-13 17:01
讲得很详细，学到了
首楼打卡
多谢支持，又更新啦，赶紧享受刷题的乐趣吧 {:10_288:} 欧拉计划 发表于 2023-5-15 05:25
多谢支持，又更新啦，赶紧享受刷题的乐趣吧
{:10_254:} #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n = 600851475143,ans;
int main()
{
for(int i=2;i<=n/i;i++)
while(n%i==0) n /= i,ans=max(ans,(LL)i);
if(n>1) ans = n;
cout<<ans<<endl;
return 0;
} {:5_93:} 大师来个 delphi的代码 分解质因数到列表，然后max 看答案 举个例子如果n为10这个输出的结果是2 小绿c 发表于 2023-5-29 00:15
举个例子如果n为10这个输出的结果是2
出师不捷啊，第三题就出纰漏了！
确实是漏了大的那个因数没有检测是否为质数，刚开始有鱼油指出时我竟然还试图反驳，最后验证一下代码，确实错了，面红耳赤、面红耳赤…… 56
用循环嵌套 zhangjinxuan 发表于 2023-5-13 17:00
这个数据怎么这么熟悉
绕了一圈，发现了终极优化方案，而且小学就学过了……
代码解析已经修改~
{:10_266:} 欧拉计划 发表于 2023-5-30 19:48
绕了一圈，发现了终极优化方案，而且小学就学过了……
代码解析已经修改~
{:10_277:}{:10_256:} zhangjinxuan 发表于 2023-5-30 20:33
刺激啊，复杂度已经降到 O(√n) 终极解法 这个很经典的问题，学习 学习学习