new project euler 第三题
https://fishc.com.cn/thread-228243-1-1.htmldef getyinshus(n):
return
def isprime(n):
return len(getyinshus(n)) < 3
def getprimeyinshus(n):
return
print(max(getprimeyinshus(600851475143)))
#486847
难道是我数学没学好吗…… 原因可能出在getyinshus和isprime上。getinshus函数判断的范围是0,n**0.5(向上取整)，但是质因数不一定都小于n**0.5，比如14=2*7，7>14**0.5。
getyinshus返回的并不是n所有的因数，因此isprime调用getyinshus函数判断质数会出错。比如getyinshus(14)返回，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
print(max(getprimeyinshus(600851475143)))
本帖最后由 smallwh 于 2023-7-3 13:07 编辑
不对。在 getprimeyinshus 中，i 取值范围还是0,n**0.5(向上取整)，会导致分解的因数不全。
14=1*2*7，7是14的最大质因数。但在你的程序中，getprimeyinshus返回值是 。很明显，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# 的对不对 将600851475143换成14，就会返回2,3#的方法不一定对所有数字都有效 本帖最后由 smallwh 于 2023-7-3 13:07 编辑
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#的方法不一定对所有数字都有效
所以问题出在哪 return
int(n ** 0.5) + 1改为n+1就是正确的，但这样对大数太慢了
页:
[1]