We help IT Professionals succeed at work.

How to find the largest prime?

Hello,
I want to find the largest prime of a given number.
This is my solution.
I don't like my solution because I change the variable i in the for loop.
Is there an better solution?


public class LargestPrime {

    public static int getLargestPrime(int number){
        if(number<=1){
            return -1;
        }
        int lpn=number;
        for(int i=2;i<=number;i++){
            if(number%i==0){
                lpn=i;
                number/=i;
                i=i-1;
            }
        }
        return lpn;
    }

    public static void main(String[] args) {
       System.out.println(getLargestPrime(16));
    }
}

Open in new window

Comment
Watch Question

You can include a test by Java's BigInteger.isProbablePrime( int n).
nociSoftware Engineer
Distinguished Expert 2019

Commented:

Wjat do you mean with largest prime... it looks like you are trying to find a "prime factor"... which is different from largest "prime". 

for 10 the largest prime would be 7, prime factor would be 5.


indeed in a loop incrementing i one should NEVER decrement i inside the loop. 


Anyway you can just drop the the line... once you have removed all common factors you can move to the next...



Software Engineer
Distinguished Expert 2019
Commented:
public class LargestPrimeFactor { 
 
    public static int getLargestPrime(int number){ 
        if(number<=1){ 
            return -1; 
        } 
        int lpn=number; 
        for(int i=2;i<=number;i++){ 
            while( number%i == 0) { 
                lpn=i; 
                number/=i; 
            } 
        } 
        return lpn; 
    } 
 
    public static void main(String[] args) { 
       System.out.println(getLargestPrimeFactor(16)); 
    } 
}
AndyAinscowFreelance programmer / Consultant

Commented:

If you want the largest factor of X then we can say 

a*b = X

where a is the largest factor which means that b is the smallest factor.  So as soon as you can divide by a number greater than 1 you have found the smallest factor and the largest factor is your number divided by that value.  No requirement to change anything in your loop - just return from the function with the largest factor at that point.

Author

Commented:
Yes, I meant the largest prime factor of a given number.
ste5anSenior Developer

Commented:
Well, why do you modify it? When I'm not mistaken, then the algorithm should be

public static int LargestPrime(int number)
{
	int upperBoundary = number;
	int remainder = number;
	int result = number;
	for (int factorCandidate = 2; factorCandidate <= upperBoundary; factorCandidate++)
	{
		if (remainder % factorCandidate == 0)
		{                    
			remainder /= factorCandidate;
			result = factorCandidate;
			upperBoundary = remainder;
		}
	}

	return result;
}

Open in new window

Cause you want only the largest factor and not the number of occurrences. Modifying the factorCandidate (your i) is only necessary when you want to count the number of occurrences.

p.s. the usage of upperBoundary and remainder can be optimized.