PE0003: Largest Prime Factor

题目

The prime factors of 13195 are 5, 7, 13, and 29. What is the largest prime factor of the number 600851475143?

问题描述

题目要求：给定一个合数（如600851475143），找到它的最大质因数。 示例：13195的质因数为5、7、13、29，最大质因数是29。

解答

方法一：基础试除法（适合小数据）

思路：从2开始逐个试除，记录能整除的最大质数。若剩余数>1，则其本身为质数，直接作为最大质因数。

import math

def find_largest_prime_factor(n):
    assert n > 1, "输入必须大于1"
    largest_factor = 1
    for i in range(2, math.isqrt(n) + 1):  # 只需检查到sqrt(n)
        while n % i == 0:                  # 完全除尽当前质因数
            largest_factor = i
            n //= i
    if n > 1:  # 剩余n本身是质数
        largest_factor = n
    return largest_factor

result = find_largest_prime_factor(600851475143)
print(result)  # 输出：6857

6857

优点：逻辑简单，适合理解质因数分解原理。 缺点：未优化时需遍历所有数，大数效率低。

优化试除法（效率翻倍）

核心优化：单独处理2，2是唯一的偶质数，先除尽2，后续只需检查奇数。

def optimized_largest_prime_factor(n):
    if n % 2 == 0:
        largest_factor = 2
        while n % 2 == 0:
            n //= 2
    else:
        largest_factor = 1
    
    factor = 3
    max_factor = math.isqrt(n)
    while n > 1 and factor <= max_factor:
        if n % factor == 0:
            largest_factor = factor
            while n % factor == 0:
                n //= factor
            max_factor = math.isqrt(n)  # 更新平方根上限
        factor += 2  # 只检查奇数
    
    if n > 1:
        largest_factor = n
    return largest_factor

result = optimized_largest_prime_factor(600851475143)
print(result)  # 输出：6857

6857

优点：时间复杂度降低50%，适合千万级数据。

方法三：numpy

思路：利用 numpy的向量化运算，快速筛选质因数。

import numpy as np
def s3(n):
    assert n > 1, "Input must be greater than 1"
    ranges= np.array(range(2, math.isqrt(n) + 1))
    factors= ranges[n % ranges == 0]
    while True:
        if np.any(factors[-1] % factors[:-1] == 0):
            factors= factors[:-1]
        else:
            break

    return int(factors[-1])

n= 600_851_475_143
s3(n)

6857

答案

答案为6857。