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.

Answer 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)

Answer 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.

Answer 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

Answer 4

One simple (but highly inefficient) approach without recursion would be: (please excuse my python syntax).

Assuming isPrime(k) is a function that returns true if k is prime. It can be implemented using sieve of Erastosenes.

def prime(n):
  i=0;
  largestPrimeFactor = -1;
  for i in range(2,n/2):
     if( isPrime(i) && n%i==0 ) :
         largestPrimeFactor = i;
  print("The highest prime factor is: "),largestPrimeFactor

Answer 5

I can stop your code getting tuck in a loop as follows.
The main problem with the stuck in a loop is the while(n!=2) (or 1 or whatever) is that you don't change n.
Note - it still won't give you prime numbers

def prime(n):
  i=0
  if(n==2):
    print "The highest prime factor is 2"
    return
  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)

Search SO with '[python] primes' for lots of ways to do this properly.

Answer 6

consider this code snippet in C, this is a very efficient algorithm for finding the largest prime factor of a number.

The functions are self-explanatory.

int isPrime(long long int n)
{
    long long int i;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
            return 0;
    return 1;
}

long long int findLargestPrimeFactor(long long int n)
{
    long long int counter=2;
    while(n!=1)
    {
        if(isPrime(n))
            return n;
        while(n%counter==0)
            n/=counter;
        counter++;
   }
   return counter-1;
}

Answer 7

The code can be further optimized as shown below, its written in php but the logic seems fair

for($div=2;$div<=sqrt($n);$div++)
{
    if($n%$div==0)
    {
        $n = $n/$div;
        $div--;
    }
}

by taking the sq root , you avoid the uncecessary looping.