当前位置: 首页 > 知识库问答 >
问题:

大数上的最大素因子失败

尉迟安民
2023-03-14

我在研究Euler项目的问题,这是问题五:

最大素因子问题3 13195的素因子为5、7、13和29。

600851475143的最大质因数是什么?

我得到了工作代码:

def factor(x, f=2):


    while x >= f*f:
        while x % f == 0:
            x = int(x/f)
        factor = f
        f += 1

    print(f'x = {x},\nlast factor = {factor}') # print for debug only 
    return max(x, factor)

因数(19*19*19*19*19*19*19*19*19*1999989899)

x=33170854034208712,最后一个系数=182128674

33170854034208712

有人知道为什么这没有得到正确的答案吗?

共有2个答案

傅穆冉
2023-03-14

我只是从头开始思考这个问题。下面是我的代码,看起来很像你的

def largest_prime_divisor(x, f=2):
    while f**2 <= x:
        if x % f == 0:
            x //= f
        else:
            f+=1
    return x

print(largest_prime_divisor(25)) # 5
print(largest_prime_divisor(13195))  # 29

n = 19*19*19*19*19*19*19*19*19*1999989899
print(largest_prime_divisor(n))  # 577 this is prime
谷善
2023-03-14

您应该使用整数除法运算符//而不是浮点除法运算符/

除此之外,您的代码是正确的

            while x % f == 0:
                x = int(x//f)
            factor = f

输出

x = 577,
last factor = 541

除法运算符差异

Python 3.7.1 (default, Nov  6 2018, 18:46:03) 
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 
>>> 
>>> print(645372136089564734321//19)
33966954531029722859
>>> print(645372136089564734321/19)
3.396695453102972e+19
 类似资料:
  • 我试图解决这个问题:https://www.hackerrank.com/contests/projecteuler/challenges/euler003/submissions/code/2977447 13195的质因数是5、7、13、29。 给定数N的最大素因子是什么? 输入格式第一行包含T,测试用例数。后面是T行,每行包含一个整数N。 每个测试用例的输出格式,显示N的最大素因子。 约束条

  • 这就是Euler项目的问题3。对于那些不知道的人,我必须找出最大的素因子600851475143。我有以下代码: 但是,当我用比600851475143小(很多)的东西测试程序时,比如100000000,那么程序需要时间——事实上,100000000到目前为止已经花了20分钟,而且还在继续。很明显,我在这里的做法是错误的(是的,这个程序确实有效,我用较小的数字进行了尝试)。有人能提出一种不那么详尽

  • O(n^2)算法简单。有没有人对此有更好的算法?

  • 我试图解决欧拉项目问题3,即: 13195的主要因子为5、7、13和29。数字600851475143中最大的素因子是什么? 这是我的解决方案,它适用于较小的值,但对于所需的数字却无法完成:

  • 在一本书(算法导论,但我不记得是哪一章)中,我学到了求解两元素间最大差值问题: 两个元素之间的最大差,使得较大的元素出现在较小的数之后。 查找数组(至少包含一个数字)中和最大的相邻子数组。 例如,给定数组[-2,1,-3,4,-1,2,1,-5,4],相邻子数组[4,-1,2,1]的最大和=6。 为了解决的两元素间最大差异问题,可以将其转化为数组的最大子数组问题: 我在想为什么。