I wrote a simple factoring program using int. Converting it to BigInteger (SAME structure!) does not work! Why not?

Question

I don't get an error when I compile, but it doesn't actually FACTOR! However, it will print the line "Testing" which I put in there to make sure it was running at all. Here's the code:

    import java.math.BigInteger;

public class test {   
public static void main(String[] Args) {

System.out.println("Testing");

BigInteger a=BigInteger.valueOf(99);
BigInteger i=BigInteger.valueOf(1);

while (i.compareTo(a) < 0 ) {

  if ((a.mod(i)) == BigInteger.ZERO) {
  System.out.println(i);
  i=i.add(BigInteger.ONE);}

  else {i=i.add(BigInteger.ONE);}
 }
  }
}

This is NOT for a homework assignment; I'm a nerd trying to factor something larger than 64 bits! I took VB in college instead of Java, so I've not worked with BigInteger before today.

Answer 1

I tried running the exact code you gave on OpenJDK 7 and got the following output:

Testing
1
3
9
11
33

It could be that your JRE's implementation of BigInteger creates new instances of BigIntegers for zeros, rather than re-using the existing BigInteger.ZERO instance. You should use .equals() instead of == to compare objects; this should work even if you have two instances of zero.

Answer 2

I would also highly recommend not looping through the entire BigInteger a. Instead, you should only loop through half that value, because for any number N, N/2 is the largest possible factor. The more optimized code becomes:

BigInteger maxFactor = a.divide(new BigInteger("2"));
while (i.compareTo(maxFactor) <= 0 ) {
  if ((a.mod(i)).equals(BigInteger.ZERO))
    System.out.println(i);
  i=i.add(BigInteger.ONE);
}

You can optimize it heaps more with a bit of number theory, but I can't really help you there.