2
\$\begingroup\$

This finds the prime factors of a number given in a variable. Is it efficient or in need of improvement?

public class PrimeFactorFinder {
    public static void main(String args[]){
        long n = 18;
        long md = 2;
        while(n!=java.lang.Math.sqrt(n)){

            if(n%md==0){
                System.out.print(" "+md);
                n /= md;
            } else {
                md++;
            }
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

The efficiency can be improved. As Simon already said, the condition

n != java.lang.Math.sqrt(n)

is equivalent to n != 1, and therefore not of much use. Perhaps you meant something different: A composite number \$ n > 1 \$ must have a prime factor \$ p \$ for which \$ p \le \sqrt n \$. Therefore, as soon as md > java.lang.Math.sqrt(n) in your iteration, n is either equal to 1 or a prime number.

The code then is

    long md = 2;
    while (md <= java.lang.Math.sqrt(n)) {
        if (n % md == 0) {
            System.out.print(" " + md);
            n /= md;
        } else {
            md++;
        }
    }
    if (n > 1) {
        System.out.print(" " + n);
    }

which reduces the number of iterations considerably: For n = 64_548_621 the loop runs until md = 283 instead of md = 25343.

Another small improvement is to repeatedly test a possible factor in a while-loop, in order to save some square root computations of the (updated) number n:

    long md = 2;
    while (md <= java.lang.Math.sqrt(n)) {
        while (n % md == 0) {
            System.out.print(" " + md);
            n /= md;
        }
        md++;
    }
    if (n > 1) {
        System.out.print(" " + n);
    }

A simple measure to reduce the number of iterations to about 50% is to test the factor 2 separately, and then only odd numbers starting at 3:

    while (n % 2 == 0) {
        System.out.print(" " + 2);
        n /= 2;
    }
    long md = 3;
    while (md <= java.lang.Math.sqrt(n)) {
        while (n % md == 0) {
            System.out.print(" " + md);
            n /= md;
        }
        md += 2;
    }
    if (n > 1) {
        System.out.print(" " + n);
    }

As pointed out by @CodesInChaos in a comment, computing the square root of a long integer via floating point arithmetic can suffer from rounding issues. This would be an issue for numbers greater than 2^52. From the analysis at How can you easily calculate the square root of an unsigned long long in C? it follows that the difference between (long)java.lang.Math.sqrt(n) and the correct value \$ \lfloor \sqrt n \rfloor \$ is at most one. Since only an upper bound is needed, replace the loop condition by

    while (md <= java.lang.Math.sqrt(n) + 1) {

If you want reusable code then move the computation of the prime factors in a separate function which returns the list of primes. This also separates the computation from the I/O and keeps the main function short:

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class PrimeFactorFinder {

    public static void main(String args[]){
        long n = 64_548_621;
        List<Long> factors = primeFactors(n);
        System.out.println(Arrays.toString(factors.toArray()));
    }

    static List<Long> primeFactors(long n) {
        List<Long> factors = new ArrayList<Long>();
        long md = 2;
        while (n % md == 0) {
            factors.add(md);
            n /= md;
        }
        md = 3;
        while (md <= java.lang.Math.sqrt(n) + 1) {
            while (n % md == 0) {
                factors.add(md);
                n /= md;
            }
            md += 2;
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ The condition while (md <= java.lang.Math.sqrt(n)) still has the downside that it does the sqrt calculation (but in your case it might be worth it). But I like most parts of your answer, I thought about some of it but forgot it while I was writing your review. \$\endgroup\$ – Simon Forsberg Sep 4 '16 at 14:16
  • \$\begingroup\$ @SimonForsberg: Thanks! – The rounding issues can be solved, but if (md <= n/md) is indeed slightly faster. I also tried to pre-calculate the square root and recompute it only if n changes, but that made no difference. \$\endgroup\$ – Martin R Sep 4 '16 at 15:12
3
\$\begingroup\$
        while(n!=java.lang.Math.sqrt(n)){

As others have suggested, this could be either

        while (n > 1) {

or

        while (md <= java.lang.Math.sqrt(n)) {

The former is simple to calculate but requires incrementing the potential factor to n. The latter only requires increment to the square root of n but is computationally expensive. Consider

        while (md * md <= n) {

That also iterates until md is greater than the square root of n but is cheaper to compute repeatedly. You'd normally only take the square root if you were doing it outside the loop:

        long limit = (long)java.lang.Math.sqrt(n);

But in this case, n decreases and could be less than the square root of the original n. So it makes sense to do the md * md <= n check. Or

         while (md <= n / md) {

This is mathematically equivalent (so long as md is positive), and it might be computationally cheaper. Some systems always calculate both n / md and n % md whenever calculating either one. So doing both together is no more expensive than doing just one. And you do n % md on every iteration of the loop already.

\$\endgroup\$
5
  • \$\begingroup\$ You are generally right about the performance difference between md <= java.lang.Math.sqrt(n) and md <= n / md, but it is not as large as one might think. I could measure no noticeable difference for the "large prime" 1099511627791, and for the "very large prime" 1152921504606847009 is was approximately 13 vs. 14 seconds. \$\endgroup\$ – Martin R Sep 4 '16 at 13:04
  • 1
    \$\begingroup\$ md <= java.lang.Math.sqrt(n) suffers from rounding issues. md * md <= n suffers from overflows if n is close to the maximum long can represent. \$\endgroup\$ – CodesInChaos Sep 4 '16 at 13:30
  • \$\begingroup\$ @CodesInChaos: Here stackoverflow.com/a/18501209/1187415 is an interesting approach to compute the integer square root correctly. \$\endgroup\$ – Martin R Sep 4 '16 at 14:41
  • \$\begingroup\$ @MartinR Since we only need an upper bound, simply adding 1 to the square-root should suffice. \$\endgroup\$ – CodesInChaos Sep 4 '16 at 14:48
  • \$\begingroup\$ @CodesInChaos: Yes, but I found that answer interesting in itself. And I think (long)java.lang.Math.sqrt(n) should be exact up to 2^52 or so (the size of the mantissa). \$\endgroup\$ – Martin R Sep 4 '16 at 14:51
3
\$\begingroup\$

This could be a bit more efficient. One thing that could be optimized is to take bigger steps when increasing md. For example, when using the input value 64_548_621 the output is:

3 3 283 25343

This means that in about 25000 iterations the code md++ was executed. If you instead would have a list of prime numbers and iterate through them, there are 2735 primes in between. However, as we're talking about computers and increasing numbers is really fast, I'm not sure if this would result in much bigger performance.


Other improvements

The condition for your while loop, n != java.lang.Math.sqrt(n) is an interesting one. And, speaking of performance, a slow one. Taking the square root of a number is not a trivial operation. As n always changes, this becomes a mathematical equation: \$n = \sqrt n\$. The solution to this equation is \$1\$. Your loop will always stop at \$1\$ (unless you input the value zero in which case it will stop at zero, or input a negative number in which case you'll end up with an infinite loop always iterating on \$-1\$). It would be much much better to just write

while (n != 1)

My last comment is about naming, it's not clear what n and md is. Is it possibly short for number and modulo? Using the names number and modulo would be better.

\$\endgroup\$
3
  • \$\begingroup\$ while (n != 1) Won't that also loop infinitely if n is less than 1? \$\endgroup\$ – mdfst13 Sep 4 '16 at 14:37
  • \$\begingroup\$ @mdfst13 Yes. Which should preferably be fixed with validating input. It could of course be changed to while (n > 1) or similar. \$\endgroup\$ – Simon Forsberg Sep 4 '16 at 16:55
  • \$\begingroup\$ thanks, I used n!=1 earlier but thought the program would take less iterations the Math.sqrt way, thanks a lot. \$\endgroup\$ – Pancake Sep 5 '16 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.