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.

fix the indentation of your code and make sure that you do not mix up whitespace and tabs. — , Oct 03 '13 at 10:53
while(n!=2): When will n be equal to 2? You are not changing n anywhere. — Abhishek Bansal, Oct 03 '13 at 10:55
As (n/i) is used in each step and when that's returned to n in the (def prime)value of n is going to decrease. That is why I had given n!=2@AbhishekBansal. Is this not allowed in python? — Dibakar Mitra, Oct 03 '13 at 11:04
That's fine, but then when it comes out of the recursive call n is n*i as before. — doctorlove, Oct 03 '13 at 11:06
In that part should I approach like this n=n/i and then call as prime(n)@doctorlove — Dibakar Mitra, Oct 03 '13 at 11:14

Traklon · Accepted Answer · 2013-10-03T12:01:10.277

3

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)

edited Oct 03 '13 at 12:01

answered Oct 03 '13 at 11:03

Traklon

301
1
8

That still gets stuck in a loop – doctorlove Oct 03 '13 at 11:06
1

Even if I'm using n!=1,the problem persists – Dibakar Mitra Oct 03 '13 at 11:07
That's what I'm asking@doctorlove,how to come out of that loop? – Dibakar Mitra Oct 03 '13 at 11:09
Ok@Traklon, the first code that you gave among the last 2 works – Dibakar Mitra Oct 03 '13 at 11:47
@Traklon in your second code you will need to check up to n/2. For example, with n = 10, answer should be 5, but your loop will stop at i = 4. – Abhishek Bansal Oct 03 '13 at 11:49
That's because the code will divide n by 2 first because 10 = 5*2. So it will stop at i = 3 for n = 5. – Traklon Oct 03 '13 at 11:54

score 1 · Answer 2 · answered Jan 28 '14 at 16:04

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.

score 1 · Answer 3 · answered Jan 28 '14 at 18:58

1

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

answered Jan 28 '14 at 18:58

brunops

555
4
5

doctorlove · Answer 4 · 2013-10-03T11:25:07.153

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.

score 0 · Answer 5 · answered Oct 03 '13 at 11:22

0

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

answered Oct 03 '13 at 11:22

Abhishek Bansal

12,589
4
31
46

Where are u taking a number as input@Abhishek Bansal and is isPrime any predefined function or the function prime that you taken is same as isPrime? – Dibakar Mitra Oct 03 '13 at 11:39
I had skipped the input part for simplicity. isPrime is another function that you will have to implement. There are numerous ways of doing so. The sieve of Erastothenes is considered one the most efficient ways. Checkout http://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python – Abhishek Bansal Oct 03 '13 at 11:43
Ok@Abhishek ..I will definitely try out – Dibakar Mitra Oct 03 '13 at 11:50

score 0 · Answer 6 · answered Sep 30 '14 at 15:26

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;
}

score 0 · Answer 7 · answered Dec 16 '15 at 07:01

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.

Right algorithm for finding largest prime factor

7 Answers7