题目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）：

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

zhangjinxuan · 发表于 2023-5-13 17:00:54

这个数据怎么这么熟悉

#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，如果还要进一步优化，可以使用欧拉筛。

zhangjinxuan · 发表于 2023-5-13 17:01:25

讲得很详细，学到了

首楼打卡

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

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

首楼打卡

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

zhangjinxuan · 发表于 2023-5-15 18:33:40

欧拉计划发表于 2023-5-15 05:25
多谢支持，又更新啦，赶紧享受刷题的乐趣吧

Kazimierz · 发表于 2023-5-16 09:19:21

#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;
}

鱼C-小师妹 · 发表于 2023-5-19 17:17:34

Eric_1891574 · 发表于 2023-5-22 20:40:16

大师来个 delphi的代码

PetalWill · 发表于 2023-5-23 07:10:41

分解质因数到列表，然后max

KentChen · 发表于 2023-5-28 07:33:03

看答案

小绿c · 发表于 2023-5-29 00:15:16

举个例子如果n为10这个输出的结果是2

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

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

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

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

whovian133 · 发表于 2023-5-29 21:19:34

56

a8634944 · 发表于 2023-5-29 23:24:48

用循环嵌套

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

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

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

代码解析已经修改~

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

欧拉计划发表于 2023-5-30 19:48
绕了一圈，发现了终极优化方案，而且小学就学过了……

代码解析已经修改~

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

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

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

Brick_Porter · 发表于 2023-6-2 07:41:47

终极解法

auend · 发表于 2023-6-2 13:47:32

这个很经典的问题，学习

bcx1001 · 发表于 2023-6-3 22:19:13

学习学习

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

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

马上注册，结交更多好友，享用更多功能^_^

评分

评分

评分

点评