Largest prime factor of a number in Java

Question

I am trying to find the Largest prime factor of a number while solving this problem here. I think that I am doing everything right, however one of the test case (#2) is failing and I can't think of any corner case where it might fail. Here's my code, please have a look and try to spot something.

public class ProblemThree
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0; i < T; i++)
        {
            System.out.println(largestPrime(scanner.nextLong()));
        }
    }

    private static long largestPrime(long n)
    {
        while (n % 2 == 0)
        {
            n = n / 2;  // remove all the multiples of 2
        }
        while (n % 3 == 0)
        {
            n = n / 3; // remove all the multiples of 2
        }

        // remove multiples of prime numbers other than 2 and 3
        while (n >= 5)
        {
            boolean isDivisionComplete = true;
            for (long i = 5; i < Math.ceil(Math.sqrt(n)); i++)
            {
                if (n % i == 0)
                {
                    n = n / i;
                    isDivisionComplete = false;
                    break;
                }
            }
            if (isDivisionComplete)
            {
                break;
            }
        }
        return n;
    }
}

Basically, what I am doing is:

Largest_Prime(n):
1. Repeatedly divide the no by any small number, say x where 0 < x < sqrt(n).
2. Then set n = n/x and repeat steps 1 and 2 until there is no such x that divides n.
3  Return n.

Answer 1

It seems you have some bug in your code as as when you input 16 largestPrime function return 1. and this is true for when input is the power of 3.

Answer 2

Detailed Algorithm description: You can do this by keeping three variables: The number you are trying to factor (A) A current divisor store (B) A largest divisor store (C) Initially, let (A) be the number you are interested in - in this case, it is 600851475143. Then let (B) be 2. Have a conditional that checks if (A) is divisible by (B). If it is divisible, divide (A) by (B), reset (B) to 2, and go back to checking if (A) is divisible by (B). Else, if (A) is not divisible by (B), increment (B) by +1 and then check if (A) is divisible by (B). Run the loop until (A) is 1. The (3) you return will be the largest prime divisor of 600851475143.

 public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        long n = in.nextLong();
        long A=n;
        long B=2;
        long C=0;
        while(Math.pow(B,2)<=A)
            {
            if(A%B==0)
                {
                C=B;
                A=A/B;
                B=2;
            }
            else
               B++;

        }
           if(A>=C)
            C=A;
           if(A==1)
               { C=2;
                break;
               }
         System.out.println(C);   
    }
}

Answer 3

Why are you removing multiples of 2 and multiples of 3? This way if you have a number that is any combination of powers of 2 and 3 you will get your answer as 1 which is clearly wrong.

For this problem you can do the naive way of looping from 2 to sqrt(n) and store the largest number which divides n, when you finish your loop just return the highest divisor you found.

Answer 4

1 drop your loop for 2 and 3. If not, you dont get 2, 2x2, 3, 2x3, ... all multiples of 2 and 3

2 change your loop to stop at 2 (and not 5):

while (n >= 2)
{

3 stop if 2

if (n==2) return 2;

4 loop from 2

and

5 loop until sqrt(n), with <= and not only < (if not, you dont get prime X Prime)

for (long i = 2; i <= Math.ceil(Math.sqrt(n)); i++)

Answer 5

One easy way of extracting prime factors is like this:

/**
 * Prime factors of the number - not the most efficient but it works.
 *
 * @param n - The number to factorise.
 * @param unique - Want only unique factors.
 * @return - List of all prime factors of n.
 */
public static List<Long> primeFactors(long n, boolean unique) {
  Collection<Long> factors;
  if (unique) {
    factors = new HashSet<>();
  } else {
    factors = new ArrayList<>();
  }
  for (long i = 2; i <= n / i; i++) {
    while (n % i == 0) {
      factors.add(i);
      n /= i;
    }
  }
  if (n > 1) {
    factors.add(n);
  }
  return new ArrayList<>(factors);
}

Those first loops are a problem. They will reduce all even numbers to 1 - thus missing 2 as the factor. Changing your code to use:

while (n > 2 && n % 2 == 0) {
  n = n / 2;  // remove all the multiples of 2
}
while (n > 3 && n % 3 == 0) {
  n = n / 3; // remove all the multiples of 2
}

You still have further issues - e.g. you report the largest prime factor of 25 to be 25 and the largest prime factor of 49 to be 49.

Just run this code using yours and mine to see where yours fails:

for (long i = 1; i < 1000; i++) {
  long largestPrime = largestPrime(i);

  List<Long> primeFactors = primeFactors(i, true);
  if (primeFactors.size() > 0) {
    Collections.sort(primeFactors, Collections.reverseOrder());
    long highestFactor = primeFactors.get(0);
    if (largestPrime != highestFactor) {
      System.out.println("Wrong! " + i + " " + largestPrime + " != " + primeFactors);
    }
  } else {
    System.out.println("No factors for " + i);
  }
}