[已解决]new project euler 第三题

歌者文明清理员

https://fishc.com.cn/thread-228243-1-1.html

def getyinshus(n):
    return [i for i in range(2, int(n ** 0.5) + 1) if n % i == 0]

def isprime(n):
    return len(getyinshus(n)) < 3

def getprimeyinshus(n):
    return [i for i in getyinshus(n) if isprime(i)]

print(max(getprimeyinshus(600851475143)))
#486847

难道是我数学没学好吗……

最佳答案

月排行榜 / 总排行榜

smallwh

2023-7-3 07:23:08

原因可能出在getyinshus和isprime上。getinshus函数判断的范围是0,n**0.5(向上取整)，但是质因数不一定都小于n**0.5，比如14=2*7，7>14**0.5。
getyinshus返回的并不是n所有的因数，因此isprime调用getyinshus函数判断质数会出错。比如getyinshus(14)返回[1,2]，isprime就会认为14是个质数

跳转到最佳答案楼层

smallwh

原因可能出在getyinshus和isprime上。getinshus函数判断的范围是0,n**0.5(向上取整)，但是质因数不一定都小于n**0.5，比如14=2*7，7>14**0.5。
getyinshus返回的并不是n所有的因数，因此isprime调用getyinshus函数判断质数会出错。比如getyinshus(14)返回[1,2]，isprime就会认为14是个质数

歌者文明清理员

smallwh 发表于 2023-7-3 07:23
原因可能出在getyinshus和isprime上。getinshus函数判断的范围是0,n**0.5(向上取整)，但是质因数不一定都小 ...

看完答案后进行了更改，这样对了吗

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def getprimeyinshus(n):
    return [i for i in range(2, int(n ** 0.5) + 1) if n % i == 0 and isprime(i)]

print(max(getprimeyinshus(600851475143)))

smallwh

不对。在 getprimeyinshus 中，i 取值范围还是0,n**0.5(向上取整)，会导致分解的因数不全。
14=1*2*7，7是14的最大质因数。但在你的程序中，getprimeyinshus返回值是 [1,2]。很明显，7被遗漏了。

若要避免遗漏，i 应满足1<i<=n（若n为质数，则n为n的最大质因数，所以要取n），但会导致程序运行时间长
可以使用分解质因数来代替寻找所有因数再判断是否为质数，代码如下

def fenjiezhiyinshu(n):
    if n <= 3:
        return n
    elif n % 2 == 0:
        return fenjiezhiyinshu(n//2)
    else:
        for i in range(3,n,2):
            if n % i == 0:
                return fenjiezhiyinshu(n//i)
            elif i >= int(n**0.5) + 1:
                return n

求72的质因数，我们通常可以这么做：
72÷2=36,36÷2=18,18÷2=9,9÷3=3
因此，72的最大质因数是3。这一段代码的原理与其类似，通过不断除以因数来求最大的质因数

歌者文明清理员

smallwh 发表于 2023-7-3 12:56
不对。在 getprimeyinshus 中，i 取值范围还是0,n**0.5(向上取整)，会导致分解的因数不全。
14=1*2*7，7是 ...

谢谢，你看看 3# 的对不对

smallwh

将600851475143换成14，就会返回2,3#的方法不一定对所有数字都有效

smallwh

smallwh 发表于 2023-7-3 12:56
不对。在 getprimeyinshus 中，i 取值范围还是0,n**0.5(向上取整)，会导致分解的因数不全。
14=1*2*7，7是 ...

错误改完了

歌者文明清理员

smallwh 发表于 2023-7-3 13:02
将600851475143换成14，就会返回2,3#的方法不一定对所有数字都有效

所以问题出在哪

smallwh

    return [i for i in range(2, int(n ** 0.5) + 1) if n % i == 0 and isprime(i)]

int(n ** 0.5) + 1改为n+1就是正确的，但这样对大数太慢了