欧拉计划第三题

本是古典何须时尚 2021-12-01 20:02 224阅读 0赞

标签（空格分隔）： Euler 博客

--------------------

> ### 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其中最大的是29，求600851475143的最大质因数。

第一反应是求600851475143的所有因数，然后找出里面最大的质数。

ans = []
    n = 600851475143
    max = int(n**0.5)
    for x in range(2, max):
        if n%x == 0:
            ans.append(x)
    
    print(ans)
    
    ans = [71, 839, 1471, 6857, 59569, 104441, 486847]

找因数没有什么加速的技巧，而且上面的程序本来就运行很快，但判断一个数是不是质数却有一些加速的技巧，常见的有`筛素数法`

**筛素数**

因为素数的倍数一定不是素数，所以我们在找到一个素数时可以将它的倍数排除，比如求100以内的素数：

n = 100
    L = list(range(2, n))
    ans = set()
    while L:
        x = L.pop(0)
        ans.add(x)
        i = 2
        while i*x < n:
            if i*x in L:
                L.remove(i*x)
            i += 1
    print(ans)
    ans = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

基于这种思想，我们可以在找600851475143的因数时就将合数筛去，

ans = []
    n = 600851475143
    iter_max = int(n ** 0.5)
    for num in range(2,iter_max):
        if n%num == 0:
            ans.append(num)
            n/=num
            while n%num == 0:
                n/=num # 保证n已被num除尽，此时n不会再有num*i的因数
    print(ans)
    ans = [71, 839, 1471, 6857]

最后结果是6857

转载于:https://www.cnblogs.com/lepeCoder/p/10991575.html