How to optimize this code in java?

Question

public class factorize {
public static void f(int n) {
 int i = 2;
 while( n > 1) {
 if (n%i == 0) {
 System.out.println("Factors " + i);
 n = n / i;
 }
 else {
 i++;
 }
 }
}

Hello, I am doing in java a function of factorize but it takes many times to excute,I try to see on the internet some theorems but the result is the same. Can you advise me some algorithms to excute this factorize as fast as possibile? this code takes like 2 mins.

• Louis Wasserman: If i^2 > n, you're done and n is prime.
• IdusOrtus: What is c? I dont see a declaration.
• EyeOfTheHawks: The easiest way to optimize this would be to remove IO. Don't print anything until the method is complete. IO is expensive.

Answer 1

Try this:

public static void f(int n) {
 int i = 2;
 while(i*i <= n) {
 if (n%i == 0) {
 System.out.println("Factors " + i);
 n = n / i;
 }
 else {
 i++;
 }
 }
 if (n > 1) {
 System.out.println("Factors " + n);
 }
}

This works because you can only have a single prime factor larger than sqrt(n): if you had two, their product would exceed n, since sqrt(n)*sqrt(n) = n. So it suffices to check those and then if n > 1, that remaining n is another prime factor.

Note: 2732983441203969650 is a large number that will not fit in an int. You should consider using a long if you want your algorithm to work for it. Note that its square root is also very large, and so the algorithm might still be very slow. For such large numbers, factorization is very hard. One algorithm you could try that will probably work for 64 bit numbers in decent time is Pollard's Rho algorithm.

Other things you can optimize in your code:

1. Check 2 separately and then only check divisibility by odd numbers;

2. Use the Sieve of Eratosthenes to generate primes lower than the square root of n and check for divisibility against those primes.

• HKing: Thank you but I don't understand why you do i*i<=n with i = 2.. the code works just fine.
• IVlad: @HKing - I do that in order to only go up until sqrt(n). i <= sqrt(n) => i*i <= n.
• HKing: why do you ^2 the two members of this condition?
• greybeard: @HKing: Not only does multiplication seem cheaper than getting a square root, it can easily be strength reduced in this context. (Beware of i < 0)