Questions over BigInteger?

Question

import java.math.BigInteger;
public class ProjectEuler {
    public static void main(String[] args) {
        BigInteger bi = new BigInteger("600851475143");
        int div = 7;
        while (bi.compareTo(new BigInteger("1")) != 0) {
            while (bi.mod(new BigInteger(div + "")).compareTo(new BigInteger("0")) == 0) {
                bi = bi.divide(new BigInteger(div + ""));
            }
            div += 2;
        }
        System.out.println("" + div);
    }
}

I was just looking over one of the basic but famous problems of "What is the largest prime factor of the number 600851475143". I found this solution different, i have a couple of questions on how this works.

The first condition checks whether the number equals 1 or not. From there i am not able to understand the rest of the code.
new BigInteger(div +""). why do we concatenate + "" here?

Probably the author noticed that the number isn't divisible by 2 nor 3 nor 5. It's no rocket science. — Luiggi Mendoza, Jun 16 '13 at 22:37
"From there i am not able to understand the rest of the code." - have you tried consulting the [`BigInteger` javadocs](http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html)? If so, is there anything *specific* you don't understand? — millimoose, Jun 16 '13 at 22:39
Searching for ["add empty string java"](https://www.google.com/search?q=java+add+empty+string) gives me [two](http://stackoverflow.com/questions/3626917/add-an-empty-string-vs-tostring-why-is-it-bad) [other](http://stackoverflow.com/questions/2506474/is-concatenating-with-an-empty-string-to-do-a-string-conversion-really-that-bad) SO questions and a whole bunch of other results that could shine light on that issue. — millimoose, Jun 16 '13 at 22:41
@LuiggiMendoza That raises a silly question: would that make the fastest answer to this Project Euler problem hardcoding the result you calculate beforehand? — millimoose, Jun 16 '13 at 22:44
@millimoose no indeed, it won't be faster. Just to note, I solved that problem using `long` values only, no need of `BigInteger`. — Luiggi Mendoza, Jun 16 '13 at 22:44
@LuiggiMendoza: the question might look silly for many, but i usually tell many that the "for OP it does not". Let's teach and pass wisdom.... — Thalaivar, Jun 16 '13 at 22:52
@LuiggiMendoza Haven't played around with PE much, but the solution above misses more low hanging fruit than that... — millimoose, Jun 16 '13 at 22:53
@Vinothbabu You're mashing several comments together. The "silly" question was one I raised. The OP's question is merely low quality - very vague, shows zero own research, etc. — millimoose, Jun 16 '13 at 22:54

score 2 · Accepted Answer · answered Jun 16 '13 at 22:41

How is the div = 7 decided?

The author decided to "hard-code" his knowledge of the number itself to decide that the first three primes are not among the divisors

The first condition checks whether the number equals 1 or not. From there i am not able to understand the rest of the code.

The rest of the code looks like this in "regular" integers:

while (bi % div == 0) {
    bi /= div;
}
div += 2;

new BigInteger(div +"") why do we concatenate + "" here

That is a short way of making an object a String. BigInteger has a parameter that takes String, so the alternative to this approach would be calling Integer.toString(div).

Note that this is not the most efficient solution: one could speed this up by observing that you could stop trying to divide when you reach the square root of the original number, because you can be sure that the next divisor will be the number itself.

@excellent, can you just explain the last paragraph little more, "one could speed this up by observing that you could stop trying to divide when you reach the square root of the original number, because you can be sure that the next divisor will be the number itself." — Kevin, Jun 16 '13 at 22:48
@Kevin this is better explained here: [Prime Factorization Calculator](http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization-calculator.php) — Luiggi Mendoza, Jun 16 '13 at 23:01

score 1 · Answer 2 · answered Jun 16 '13 at 22:41

How is the div = 7 decided?

Probably the author noticed that the number isn't divisible by 2 nor 3 nor 5. To know how the author did this, he/she should have known this rules: Divisibility Rules and Tests

The first condition checks whether the number equals 1 or not. From there i am not able to understand the rest of the code.

The author is making sure that the number is not BigInteger("1") since it's dividing the number and storing the results in bi in the loop iterations. Note this:

bi = bi.divide(new BigInteger(div + ""));

new BigInteger(div +""). why do we concatenate + "" here?

It uses the BigInteger(String) constructor. The author n̶a̶i̶v̶e̶l̶y̶ makes a new String by adding the int with an empty String.

Questions over BigInteger?

2 Answers2