0

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.

Yu Hao
  • 119,891
  • 44
  • 235
  • 294
Srikanth Bhandary
  • 1,707
  • 3
  • 19
  • 34

1 Answers1

4
n=600851475143 
d=2
while d < n/d:
    if n%d==0:
        n/=d
    else:
        d+=1
print n
chenzhongpu
  • 6,193
  • 8
  • 41
  • 79
  • Or even better, `d = 3` and `d += 2` considering it's not even and `2` is the only even prime number. – Yu Hao Aug 07 '15 at 05:28
  • Great it is showing correct in the website which I am referring. But I am confused with the question. But I am confused with the question. I am trying to find the all possible prime numbers for the given number, and tried to find the largest. Is it correct? Please suggest, – Srikanth Bhandary Aug 07 '15 at 05:29
  • 1
    @SrikanthBhandary you can refer to http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number – chenzhongpu Aug 07 '15 at 05:31
  • I have confused withe the prime number and prime factor. Thanks alot – Srikanth Bhandary Aug 07 '15 at 05:43