PE003.py

#!/usr/bin/env python
# -*coding:UTF-8-*-
"""
@Project ProjectEuler
@File PE003.py
@Authand Haosen Luo
@Date 2024/12/8 23:34
"""

"""
最大质因数
13195的质因数包括5、7、13和29。
600851475143的最大质因数是多少？
"""

import math
import numpy as np


def get_primer_list(n):
    """
    一个数的所有质数列表
    :param n:
    :return:
    """
    # 一个数的最大因数（因子）是平方根
    max_factor = int(math.sqrt(n))
    # 最小的质数
    base_primer = [2, 3, 5]

    flag = True

    for i in range(7, max_factor + 1, 2):
        for j in base_primer:
            if i % j == 0:
                flag = False
                break

        if flag:
            base_primer.append(i)

        flag = True

    return base_primer


def main(number):
    """
    求解一个数的所有质因数
    :param number: 
    :return: 
    """
    primers = get_primer_list(number)
    primers = np.array(primers)
    res = number % primers
    res = primers[res == 0]

    return res[-1]


def main2(number):
    max_factor = int(math.sqrt(number))
    x = np.array(range(2, max_factor + 1, 1))
    print(x)
    x = x[number % x == 0]
    print(x)

    while True:
        if np.any(x[-1] % x[:-1] == 0):
            x = x[:-1]
        else:
            break

    return x[-1]


if __name__ == '__main__':
    n1 = 13195
    print(main(n1))

    n2 = 600851475143
    print(main2(n2))