Arithmetic error in Java

Question

I recently started learning Java, and I am now trying to solve some Eulerproject problems.

The task is: What is the largest prime factor of the number 600851475143 ?

I was able to create this code, but I get an error:

Code

package exercises;
import java.util.ArrayList;

public class Euler3 {

    // Main code
    public static void main(String[] args) {


        System.out.println( getPrimeFactors(15) );
    }

    // Code for breaking a number to prime factors
    public static ArrayList getPrimeFactors(int n){

        ArrayList factors = new ArrayList();

        int d = 2;

        while(n > 1 ){
            while(n%d == 0 ){
                factors.add(d);
                n /= d;
            }
            d +=d;
        }

        return factors;
    }

}

Error:

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at exercises.Euler3.getPrimeFactors(Euler3.java:22)
    at exercises.Euler3.main(Euler3.java:9)

What am I doing wrong?
Thanks

Your logic appears to be incorrect. It will only divide by powers of 2, and eventually you get a overflow and it tries to divide by 0. — threenplusone
– threenplusone, Commented Mar 5, 2013 at 0:47

threenplusone · Accepted Answer · 2013-03-05 00:50:08Z

3

For a very naive solution, try changing the line d += d to d += 1.

answered Mar 5, 2013 at 0:50

threenplusone

2,13220 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

scaevity · Accepted Answer · 2013-03-05 01:00:26Z

3

Your d is overflowing, I printed n and d inside while (n > 1):

    15 2
    15 4
    15 8
    15 16
    15 32
    15 64
    15 128
    15 256
    15 512
    15 1024
    15 2048
    15 4096
    15 8192
    15 16384
    15 32768
    15 65536
    15 131072
    15 262144
    15 524288
    15 1048576
    15 2097152
    15 4194304
    15 8388608
    15 16777216
    15 33554432
    15 67108864
    15 134217728
    15 268435456
    15 536870912
    15 1073741824
    15 -2147483648
    15 0

I think the solution is d++, not d+=d -- right now you are only checking powers of two, not all consecutive integers.

edited Mar 5, 2013 at 1:00

scaevity

4,11113 gold badges41 silver badges58 bronze badges

answered Mar 5, 2013 at 0:54

koponk

4721 gold badge3 silver badges14 bronze badges

Comments

Jayamohan · Accepted Answer · 2013-03-05 00:52:20Z

1

The issue is your d is crossing Integer.Max limit and overflowing.

answered Mar 5, 2013 at 0:52

Jayamohan

13k2 gold badges31 silver badges41 bronze badges

Collectives™ on Stack Overflow

Arithmetic error in Java

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related