CODEWITHSUNDEEP
python-3.x
Srikanth Bhandary
Srikanth Bhandary

Reputation: 1747

Finding largest prime factor too slow in Python

Question:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

And I tried to solve it by using the below snippet, its taking long time to run. Is there any best way to solve this problem?

def find_prime(num, ranger):
    count  = 0
    prime = True
    for i in range(2, num):
        if num % i == 0:
            count = count + 1
        if count > 1:
            prime = False
            return prime
    return prime            

prime_list = [] 
target = 600851475143
for i in range(2,target ):
    if target % i == 0:
        print(i)
        if find_prime(i,target) and i % 2 == 0:
            prime_list.append(i)
            print(prime_list)

print(max(prime_list))

Please suggest.

Upvotes: 0

Views: 105

Answers (1)

chenzhongpu
chenzhongpu

Reputation: 6871

n=600851475143 
d=2
while d < n/d:
    if n%d==0:
        n/=d
    else:
        d+=1
print n

Upvotes: 4

Related Questions