Java Largest Prime Factor of Long

Question

I'm trying to find the largest prime factor of a large number. For example, if that number were 573849284703, my code would look like this:

public static void main(String[] args) {

    long number = 573849284703l;

    System.out.println(lgstprmfactor(number));

}

public static long lgstprmfactor(long number) {
    for (long i = 286924642352l; i > 0; i--) {
        if (number % i == 0 && isPrime(i) == true) {
            long answer = i;
            return answer;
        }
    }
    return 0;
}

public static boolean isPrime(long i) {
    for (long c = 2; c < i; c++) {
        if (i % c == 0)
            return false;
    }
    return true;
}

But it's taking forever to run- any suggestions to speed it up or optimize the code in general?

You might want to look at [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem) to aid in checking for primes. — Jashaszun, Jul 27 '15 at 22:15
Here is a good reference at how you might evolve your code to adapt other methods. http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number — lmcphers, Jul 27 '15 at 22:15
https://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms — Stephen C, Jul 27 '15 at 22:40
@TameHog - That is only going to be effective if you can partition the problem so that the threads don't need to synchronize. Not easy for factorization. There are better way; e.g. use a better algorithm. — Stephen C, Jul 27 '15 at 22:43

Gnarlywhale · Answer 1 · 2015-07-27T22:29:28.497

2

One quick solution to improve runtime could be to implement your algorithm in multiple threads that concurrently check if the number is a prime factor across different ranges. I.e. create a thread that checks if it is a prime factor between 0 and 1000000, then a thread for 1000001+ etc.

edited Jul 27 '15 at 22:29

answered Jul 27 '15 at 22:17

Gnarlywhale

4,030
2
15
18

1

This is suitable more as a comment and not an answer. – hmc_jake Jul 27 '15 at 22:29
2

Noted. I have only recently begun answering on stack overflow and as of yet do not have enough reputation to post comments on posts that are not my own. I went ahead with posting an answer because properly implemented multi-threading would improve the OPs runtime. – Gnarlywhale Jul 27 '15 at 22:33
1

That's fair enough. Just letting you know. – hmc_jake Jul 27 '15 at 22:41

score 2 · Answer 2 · answered Jul 27 '15 at 23:11

public static void main(String[] args)
 {
  long startTime = System.currentTimeMillis();
  System.out.println(largestprimefactor(573849284703l));
  long endTime = System.currentTimeMillis();
  System.out.println(endTime - startTime+" ms ");
 }

public static int largestprimefactor(long l)
{
    int i;
    long copyofinput = l;
    for(i=2;i<copyofinput;i++)
    {
        if(copyofinput%i==0){

            copyofinput/=i;
            i--;
        }
    }

    return i;
}

}

output : 66718903

688 ms

score 0 · Answer 3 · answered Aug 05 '15 at 19:38

The basic ideas here: remove prime factors as you find them, don't search higher than the square root of the remaining number, and skip even numbers (other than 2). I also added some error checking and other decorations.

public static void main(String[] args)
{
    try {
        System.out.println(largestPrimeFactor(573849284703l));
    } catch (ArithmeticException e) {
        System.out.println("Error factoring number: " + e.getMessage());
    }
}

private static long sqrtint(long n) {
  return (long)Math.sqrt(n + 0.5);
}

public static int largestPrimeFactor(long n) throws ArithmeticException
{
    if (n < 2) throw new ArithmeticException(n + " < 2");
    while (n%2 == 0) n /= 2;
    if (n < 2) return 2;
    long i, root = sqrtint(n);
    for(i=3; i<root; i+=2)
    {
        if(n%i == 0) {
            n /= i;
            while (n%i==0) n /= i;
            if (n == 1) return i;
            root = sqrtint(n);
        }
    }

    return n;
}

}

Java Largest Prime Factor of Long

3 Answers3