Right algorithm for finding largest prime factor

Question

I am trying to find out the largest prime factor of any number. I am doing the program for this problem in python, but there seems to be something wrong with the algorithm that I am following. It seems to fall into an infinite loop. The program goes like this:

def prime(n):
  i=0;
  while(n!=2):
    for i in range(2,n):
        if(n%i==0):
            prime(n/i);
        else:
            continue;
    print("The highest prime factor is: "),n;

print("Enter a number to find its highest prime factor");
n=input();
prime(n);

Just point out what are the problems here and also mention if there are any other better algorithm than this one for solving this.

Solution 1

EDIT : It feels like I can't manage to be clear without some code, so here it is, with a few modification from yours :

def prime(n):
  i=2
  while (n%i != 0 and i < n):
    i += 1
  if (i < n):
    return prime (n/i)
  else:
    print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor")
n=input()
prime(n)

However, your algorithm is not very efficient. For example, you might consider using Pollard's Rho if you want something better and not long to code. And even if you want to stick with your idea, you shouldn't do your divisibility tests like this. You may want to run an Erathostene sieve first to only test divisibility by prime factors. Or even only remember the last divisor you found in order to restart the algorithm from there, not from 2.

For example, a little bit better code would be :

def prime(n,a):
  i = a
  while (n%i != 0 and i*i < n):
    i += 1
  if (i*i < n):
    return prime (n/i, i)
  else:
    print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor")
n=input()
prime(n,2)

Solution 2

My solution is rather simple and deals well with huge numbers that would cause memory error in most of the solutions above.

import math

def prime(n):
    for x in range(2, int(math.sqrt(n)) + 1):
        if n % x == 0:
            print n / x
            return prime(n / x)

if __name__ == '__main__':
    prime(898563214300)

The last printed number is the largest prime factor.

Solution 3

Avoiding recursive calls:

def largest_prime_factor(number):
  if number == 1:
    return 1

  test = 2
  while number > 1:
    if number % test == 0:
      number /= test
    else:
      test += 1

  return test