CODEWITHSUNDEEP
javaprime-factoring
user3579404
user3579404

Reputation: 3

Java Largest Prime Factor of Long

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?

Upvotes: 0

Views: 369

Answers (3)

Charles
Charles

Reputation: 11499

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

}

Upvotes: 0

Archit Garg
Archit Garg

Reputation: 1012

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

Upvotes: 2

Gnarlywhale
Gnarlywhale

Reputation: 4240

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.

Upvotes: 2

Related Questions