Function doesn't response in large integer values, ln[*]

user_15359606 0
Viewed 64

I have to find the largest prime factor of a number, so I wrote the code below:

num = int(input())
start = num-2
while start>=2:
    if num%start==0 and (2**(start-1))%start==1:
        print(start)
        break
    else:
        start-=1

It works when the input isn't large. Ex. 12351264 => 128659 or 13195=>29, but I entered 600851475143 and it didn't respond for 10-15 minutes so I restart the kernel. Cpu and memory usages weren't high at that moment but fans start to make a bit noise. What is the problem with the code and how can I fix it?

Note: I used Fermat’s Little Theorem in the second condition.

jupyter-notebook python
2 Answers

A faster way to get the largest prime number is to find all prime numbers from smallest to largest, because you have to try only sqrt(n)/3 numbers in the worst case.

def iter_factors():
    yield 2
    yield 3
    for i in count(6, 6):
        yield i - 1
        yield i + 1

def prime_factors(num):
    for i in iter_factors():
        if i*i > num:
            break
        while num % i == 0:
            yield i
            num //= i
    if num > 1:
        yield num

print(max(prime_factors(600851475143)))
user_35558450

When you exceed MAXINT for your machine, Python converts the computations to its "large integer" mode, which is much slower. You're working with a number that has a huge quantity of digits. Instead, you need to perform your modulus operations regularly, or perform some other algorithm, to get the performance you'll need.

From GeeksForGeeks:

def big_power_mod(x, y, base)
    result = 1
     
    while y > 0:
         
        # If y is odd, multiply by x
        if y % 2 == 1:
            result *=  x

        # halve y; square x; reduce mod base
        y = y >> 1
        x *= x;
        x %= base

    return result
user_47851850
Related