寻找一个数的最大质因数

给定一个正整数 n (1 <= n <= 10^15)。我们的目标是找到这个数的最大质因数。

> 输入： 6

> 输出： 3

> 解释： 质因数为 2 和 3。其中最大的是 3。

>

> 输入： 15

> 输出： 5

> 解释： 质因数为 3 和 5。其中最大的是 5。

>

> 输入： 28

> 输出： 7

> 解释： 质因数为 2 和 7。其中最大的是 7。

在线练习该题目

[基础方法] 试除法

> – 首先，我们需要移除所有的因子 2，因为它是唯一的偶数质数。

> – 一旦所有的因子 2 都被移除，我们就可以从 3 开始检查奇数。

> – 我们会测试每个奇数是否是因子，并反复进行除法操作，直到该因子被完全移除。

> – 这个过程会持续进行，遍历所有小于等于 √n 的奇数。

> – 如果在所有的除法操作之后，剩下的数仍然大于 2，那么它本身就是一个质数，也就是最大的质因数。

C++

// C++ code to find largest prime
// factor of number

#include 
using namespace std;

int largestPrimeFactor(int n) {

    int largestPrime = -1;

    // Check for factors of 2
    while (n % 2 == 0) {
        largestPrime = 2;
        n /= 2;
    }

    // Check for odd factors starting from 3
    for (int i = 3; i * i  2) {
        largestPrime = n;
    }

    return largestPrime;
}

int main() {
    int n = 15;
    int res = largestPrimeFactor(n);
    cout << res << endl;

    return 0;
}

CODEBLOCK_b0bf3bf8


Python

# Python code to find largest prime
# factor of number

def largestPrimeFactor(n):
    largestPrime = -1

    # Check for factors of 2
    while n % 2 == 0:
        largestPrime = 2
        n //= 2

    # Check for odd factors starting from 3
    i = 3
    while i * i  2:
        largestPrime = n

    return largestPrime

if __name__ == "__main__":
    n = 15
    res = largestPrimeFactor(n)
    print(res)

CODEBLOCK_28592a01


JavaScript

// JavaScript code to find largest prime
// factor of number

function largestPrimeFactor(n) {
    let largestPrime = -1;

    // Check for factors of 2
    while (n % 2 === 0) {
        largestPrime = 2;
        n /= 2;
    }

    // Check for odd factors starting from 3
    for (let i = 3; i * i  2) {
        largestPrime = n;
    }

    return largestPrime;
}

let n = 15;
let res = largestPrimeFactor(n);
console.log(res);

`

输出

5

时间复杂度： O(sqrt(n))。
辅助空间： O(1)

[优化方法] 优化的试除法

> – 该方法首先移除所有的因子 2 和 3 以简化后续步骤。