[已解决]new project euler 第三题

歌者文明清理员

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

1. def getyinshus(n):
   
2.     return [i for i in range(2, int(n ** 0.5) + 1) if n % i == 0]
   
3. 
   
4. def isprime(n):
   
5.     return len(getyinshus(n)) < 3
   
6. 
   
7. def getprimeyinshus(n):
   
8.     return [i for i in getyinshus(n) if isprime(i)]
   
9. 
   
10. print(max(getprimeyinshus(600851475143)))
    
11. #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(向上取整)，但是质因数不一定都小 ...

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

1. def isprime(n):
   
2.     for i in range(2, int(n ** 0.5) + 1):
   
3.         if n % i == 0:
   
4.             return False
   
5.     return True
   
6. 
   
7. def getprimeyinshus(n):
   
8.     return [i for i in range(2, int(n ** 0.5) + 1) if n % i == 0 and isprime(i)]
   
9. 
   
10. 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），但会导致程序运行时间长
可以使用分解质因数来代替寻找所有因数再判断是否为质数，代码如下

1. def fenjiezhiyinshu(n):
   
2.     if n <= 3:
   
3.         return n
   
4.     elif n % 2 == 0:
   
5.         return fenjiezhiyinshu(n//2)
   
6.     else:
   
7.         for i in range(3,n,2):
   
8.             if n % i == 0:
   
9.                 return fenjiezhiyinshu(n//i)
   
10.             elif i >= int(n**0.5) + 1:
    
11.                 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

1.     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就是正确的，但这样对大数太慢了