CODEWITHSUNDEEP
java
urlawyer
urlawyer

Reputation: 13

Project Euler problem 10, wrong answer but why (Java)

newbie question I know, but I can't figure out what the error is in my code for this question. The problem asks to get the sum of all prime numbers below 2,000,000.

I can't figure out why my code works for smaller sets, yet when I wait patiently for my code to finish for 2,000,000 it spits out a wrong answer. 1,179,908,154 in this case.

DISCLAIMER I realize the code I've written is extraordinarily inefficient/wasteful and that I should use the Sieve of Eratosthenes among other things. I'm just trying to figure out why it gives the wrong answer.

    public static void main(String args[]) {
        
        int[] primes = new int[2000000];
        int index=0;
        int ans=0;
        
        //finding primes and populating array
        for (int candidate=2; candidate<=2000000; candidate++) {
            System.out.println(candidate); //so I can watch the numbers go up
            for (int divisor=1; divisor<=candidate; divisor++) {
                
                if (candidate%divisor==0 && candidate==divisor) {
                    primes[index]=candidate;
                    index++;
                    break;
                }
                
                if (candidate%divisor==0 && candidate!=divisor && divisor!=1) {
                    break;
                }               
                
            }
        }
        
        //adding primes
        for (int m=0; m<primes.length; m++) {
            ans+=primes[m];
        }
        
        System.out.println(ans);
    }

Upvotes: 1

Views: 165

Answers (2)

Alonso del Arte
Alonso del Arte

Reputation: 1025

I get the same wrong result with my Java program loaded into my local Scala REPL.

scala> org.oeis.primes.PrimeLister.listPrimes(2_000_000)
res3: java.util.ArrayList[Integer] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

scala> import collection.JavaConverters._
import collection.JavaConverters._

scala> res3.asScala
       ^
       warning: object JavaConverters in package collection is deprecated (since 2.13.0): 
Use `scala.jdk.CollectionConverters` instead
res4: scala.collection.mutable.Buffer[Integer] = Buffer(2, 3, 5, 7, 11, 13, 17, 19, ...

scala> res4.toList
res5: List[Integer] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

scala> res5.scanLeft(0)(_ + _)
res7: List[Int] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...

scala> res5.scanLeft(0L)(_ + _)
res12: List[Long] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...

scala> res7.takeRight(1)
res15: List[Int] = List(1179908154)

scala> res12.takeRight(1)
res16: List[Long] = List(142913828922)

So yeah, try using long to add up the primes.

Upvotes: 0

Dante Culaciati
Dante Culaciati

Reputation: 143

I think your problem lies within the type of ans.

In Java, ints are 4 bytes long, which means they can only store numbers ranging from -2,147,483,648 to 2,147,483,647. The sum of all prime numbers below two million is far greater than these values. What's happening here is that your int variable overflows and "goes around" (it "skips" from the maximum value to the minimum value).

Try changing the type of ans to long.

Upvotes: 1

Related Questions