题目3：找出一个合数的最大质数因子

欧拉计划 · 发表于 2023-5-12 18:55:52

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 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 的最大质数因子是多少？

视频讲解：

思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

欧拉计划 · 发表于 2023-5-15 05:25:46

zhangjinxuan 发表于 2023-5-13 17:01
讲得很详细，学到了

首楼打卡

多谢支持，又更新啦，赶紧享受刷题的乐趣吧

欧拉计划 · 发表于 2023-5-29 02:41:31

小绿c 发表于 2023-5-29 00:15
举个例子如果n为10这个输出的结果是2

出师不捷啊，第三题就出纰漏了！

确实是漏了大的那个因数没有检测是否为质数，刚开始有鱼油指出时我竟然还试图反驳，最后验证一下代码，确实错了，面红耳赤、面红耳赤……

欧拉计划 · 发表于 2023-5-30 19:48:05

zhangjinxuan 发表于 2023-5-13 17:00
这个数据怎么这么熟悉

绕了一圈，发现了终极优化方案，而且小学就学过了……

代码解析已经修改~

欧拉计划 · 发表于 2023-5-31 01:27:44

zhangjinxuan 发表于 2023-5-30 20:33

刺激啊，复杂度已经降到 O(√n)

账号		自动登录	找回密码
密码			立即注册