Largest prime factor on huge number failed

Question

I was working on Euler Project problems, this is problem five:

Largest prime factor Problem 3 The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

I got the working code:

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)

factor(19*19*19*19*19*19*19*19*19*1999989899)

x = 33170854034208712, last factor = 182128674

33170854034208712

Does anyone know why this failed to yield the right answer?

(x = 33170854034208712, last factor = 182128674) is this the answer you got? Just verifying because I ran your code and retrieved: x = 6857, last factor = 1471 — Kryesec, Dec 14 '18 at 02:43
Hey, Mat! Can you tell us what is the expected result? `1999989899` is not a prime number: `1999989899 = 577 * 541 * 149 * 43` — JoshuaCS, Dec 14 '18 at 03:01
Check out this[thread](https://stackoverflow.com/a/22808285/7018885). I think it will resolve the issue on Huge numbers! — Mohammad Albakri, Dec 14 '18 at 03:13
That is the wrong answer from my wrong code. the right answer is just as tooTired mentioned below. — Matt Cao, Dec 14 '18 at 05:36

JoshuaCS · Answer 1 · 2018-12-14T03:16:10.633

0

I just reasoned about the problem from scratch. Below is my code, it seems much like yours

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

edited Dec 14 '18 at 03:16

answered Dec 14 '18 at 03:08

JoshuaCS

2,524
1
13
16

score 0 · Accepted Answer · answered Dec 14 '18 at 03:08

You should use the integer division operator // rather then the float division operator /

Other than that your code is correct

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

Output

x = 577,
last factor = 541

Division operator difference

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

Thanks, I actually figure this out after a little hacking and research myself, I did not realize the floor division does what I want. I even thought about import python27 division function. Such a funny thought! — Matt Cao, Dec 14 '18 at 05:31

Largest prime factor on huge number failed

2 Answers2