Project Euler #3 Efficiency

Question

I'd like to reduce the complexity of my code

Problem :

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of a given number N?

Solution :

import java.util.Scanner;
import java.util.TreeSet;
public class Solution {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int testCases = sc.nextInt();
 for (int i = 0; i < testCases; i++) {
 int input = sc.nextInt();
 System.out.println(calculateFactors(input));
 }
 }
 public static int calculateFactors(int input) {
 TreeSet<Integer> set = new TreeSet<>();
 while (input % 2 == 0) {
 set.add(2);
 input = input / 2;
 }
 for (int i = 3; i < Math.sqrt(input); i = i + 2) {
 while (input % i == 0) {
 set.add(i);
 input = input / i;
 }
 }
 if (input > 2) {
 set.add(input);
 }
 int max = set.last();
 return max;
 }
}

• bcrist: Efficiency and complexity are not exact antonyms.
• itsjeyd: Is it just me or does the title of your question read like the title of a Big Bang Theory episode?

Answer 1

Correctness:

Project Euler Problem #3 asks for the largest prime factor of 600851475143, and that number exceed the range of the int data type. (Your program aborts with an exception for this input value.) You have to use long instead.

In

for (int i = 3; i < Math.sqrt(input); i = i + 2) { ... }

the < should be replaced by <=, otherwise you get a wrong result if the input is the square of a prime number (such as 25). To avoid a loss of precision if input is converted to a floating point number, it should be

for (long i = 3; i * i <= input; i = i + 2) { ... }

Efficiency:

The problem is about the largest prime factor. Your algorithm already determines the prime factors in increasing order. Therefore there is no need to store the prime factors in a collection to get its maximum value. It is sufficient to remember the last prime factor found.

Putting it together:

Your function (renamed slightly) would then look like

public static long calculateLargestFactor(long input) {
 long largestFactor = 1;
 while (input % 2 == 0) {
 largestFactor = 2;
 input = input / 2;
 }
 for (long i = 3; i * i <= input; i = i + 2) {
 while (input % i == 0) {
 largestFactor = i;
 input = input / i;
 }
 }
 if (input > 2) {
 largestFactor = input;
 }
 return largestFactor;
}

Answer 2

for (int i = 3; i < Math.sqrt(input); i = i + 2) {

You're computing sqrt on each iteration, which wastes more time then the useful work (modulus computation) takes. Using

for (long i = 3; i * i <= input; i = i + 2) {

is fine(*), as multiplication is much faster than division, using something like

long limit = (long) Math.ceil(Math.sqrt(input));
for (long i = 3; i <= limit; i = i + 2) {

is possibly better.

---

(*) Note that input changes during the iterations and the correctness is not obvious. Fortunately, it's correct.

I guess, the fastest solution (apart from smarter and complicated algorithms) would be using the limit as above and recomputing it whenever a divisor is found. But it's no big improvement.