-3

I want to find largest prime factor of 600851475143.

But range in my code doesn't work for 600851475143 , too big number .

What should I do? Is there any more efficient algorithm?

list=[]
for i in range(1,600851475144):
    count = 0
    if 600851475143 % i == 0:
        for x in range(2,i):
            if i % x == 0:
                count+=1
                print(count)
        if count == 0:
            list.append(i)
        count=0
print(list)
juanpa.arrivillaga
  • 88,713
  • 10
  • 131
  • 172
KYH
  • 37
  • 1
  • 6
  • See the [**`continue`**](https://docs.python.org/3/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops) keyword to simplify your loop, and use [**`xrange`**](https://docs.python.org/2/library/functions.html#xrange) instead of **`range`**. – Peter Wood Sep 01 '16 at 06:54

1 Answers1

1

This will do :

def PrimeFactor(n):
    m = n
    while n%2==0:
        n = n//2
    if n == 1:         # check if only 2 is largest Prime Factor 
        return 2
    i = 3
    sqrt = int(m**(0.5))  # loop till square root of number
    last = 0              # to store last prime Factor i.e. Largest Prime Factor
    while i <= sqrt :
        while n%i == 0:   
            n = n//i       # reduce the number by dividing it by it's Prime Factor
            last = i
        i+=2
    if n> last:            # the remaining number(n) is also Factor of number 
        return n
    else:
        return last
print(PrimeFactor(int(input())))
Kalpesh Dusane
  • 1,477
  • 3
  • 20
  • 27
  • Thank u so much! It works! But I can't understand why we use sqrt.. Is that a mathematical technique? – KYH Sep 01 '16 at 08:08
  • 1
    @KYH: why should you check *after* reaching the square root? After that, for all `a*b` results, `a` is going to be larger than `sqrt(target)` and `b` is going to be smaller. But you already checked all possible values for `b` in the first 'half' – as `a`! – Jongware Sep 01 '16 at 08:34
  • 1
    @KYH: to check number is prime or not you check till number's square root for efficient time so this is also applicable here.. and also as explained by above comment (by Rad Lexus) – Kalpesh Dusane Sep 01 '16 at 09:05