Hello DaniWeb community! I am writing code for problem 10 of Project Euler. I have decided that the Sieve of Eratosthenes was the best option for creating a list of primes less than two million. Here is my code (yes, I mis-spelled Sieve and Eratosthenes):

package projecteulerjava;

class ProblemTen
{
	public ProblemTen()
	{
		boolean Primes[] = Erasthones(2000000);
		int     Total    = 0;
		for (int i = 2; i < Primes.length; i ++)
		{
			if (!Primes[i])
			{
				boolean IsPrime = Primes[i];
				Total += i;
			}
		}
		
		System.out.println("The sum of the primes up to two million is " + Total);
		
	}
	
	public static boolean[] Erasthones(int ToWhat)
	{
		boolean Seive[] = new boolean[ToWhat + 1];
		
		int PrimeAt    = 2;
		int Multiplier = 2;
		
		while (PrimeAt <= ToWhat)
		{
			while ((Multiplier * PrimeAt) < (ToWhat - 1))
			{
				Seive[Multiplier * PrimeAt] = true;
				Multiplier ++;
			}
			
			Multiplier = 2;
			
			for (int i = PrimeAt + 1; i < Seive.length; i ++)
			{
				if (Seive[i] == false)
				{
					PrimeAt = i;
					break;
				}
			}
			
			if (PrimeAt == ToWhat)
			{
				break;
			}
		}
		
		return Seive;
	}
}

Okay. So I ran this code -- first time I got a promising result. Apparently -- and I have done research -- the result it gives me, 1183908153, is wrong. I immediately turned towards the debugger (using NetBeans 7.0). Upon close investigation, my Sieve is working perfectly, which leads to an interesting question: How was my summing method wrong? TO THE DEBUGGER! As soon as I turned the debugger on and set its breakpoints in the for loop to sum, it started to work perfectly, so we now are at my predicament -- it works with the debugger, and does not without it. Needles to say, I am awfully confused and would greatly appreciate any help you could give me.

EneilShade

What is the correct sum of primes? What is the difference between what you compute and the correct answer?

Is the correct answer 142917828921?
If so, you may want to compare this with the largest value an int (eg int Total=0; ) can hold...

Edited 5 Years Ago by JamesCherrill: n/a

The problem is, unless the debugger is on, it thinks all numbers are primes.

it thinks all numbers are primes.

Can you show this by adding printlns, reducing the number to check to a small number and see what is printed out?

I have most definitely tried that. I do not come for help unless I have debugged for hours on my own. When the debugger is not attached, it shows that no numbers have been eliminated as primes. Every index in my boolean array is "false", meaning prime in my case. Rather strange a problem. As soon as I attach a debugger, it prints the proper values and adds correctly.

Here is what I get when I print out the found primes:
prime: i=2
prime: i=3
prime: i=5
prime: i=7
prime: i=11
prime: i=13
prime: i=17
prime: i=19
prime: i=23
prime: i=29
prime: i=31
prime: i=37
prime: i=41
prime: i=43
prime: i=47
prime: i=49 <<<<<<<<< 7*7 Last 2 are bad!!!!!!!!!
prime: i=50 <<<<<<<<<<<<<<<<< NOTE!!!!

This was the last few for 100 numbers:
prime: i=83
prime: i=89
prime: i=97
prime: i=99 <<<<<<< last 2 are bad!!!
prime: i=100

here I only printed if in the last 10 values
prime: i=1999993
prime: i=1999999
prime: i=2000000

There is something wrong with your debugging technique. Can you post the code you've used for debugging? I get the above which looks reasonable except for the last 2 numbers.

I have removed the print code. But thanks for the post! That is an interesting bug! I will check that out. Now, why, though, does it work in the debugger?!

why, though, does it work in the debugger?

It should work in the debugger. Why do you think it shouldn't?

No, it does work when I use the debugger. It does not work (at all) when I do not use the debugger.

It does not work (at all) when I do not use the debugger.

Can you post the code you are talking about? That does not work. I can't understand how the debugger could change how it executes.
I copied, compiled and executed the code you posted earlier and it seems to work up to the last 2 items.

Edited 5 Years Ago by NormR1: n/a

I encounter does not work at all for that code. Well, if that code seems flawed only to the last two items, I will fix that. This thread is solved.

Have you changing the declaration of int Total to long Total? As I posted before, the correct answer is too large for an int. It may be that he debugger is picking up the integer overflow whereas the normal JRE doesn't check for that???

Edited 5 Years Ago by JamesCherrill: n/a

Here is what I get when I print out the found primes:

prime: i=49 <<<<<<<<< 7*7 Last 2 are bad!!!!!!!!!
prime: i=50 <<<<<<<<<<<<<<<<< NOTE!!!!

Hi norm. What was your runtime environment for this test? I ran the same code with J1.6u26 under Eclipse, both normal execution and under the debugger and all my primes looked good (including the last two!). All I had to do was change the declaration of Total to get what looks like the right final answer.
I left the sieve method alone and printed the primes in the constructor. Did you patch the sieve method to limit your test?

JamesCherrill, you are a genius with the change "int" to "long"... I completely missed that! Good catch man, and fixed all my problems too!

@James
I don't have an IDE. I compile with an old version of JVC using a JDK 1.4 library (compile time is <<<< 1sec). I had to change the logic to get the last two primes to be correct. It now appears to get all good numbers including the last few.
For example here is the output for 20 numbers:

Running: "C:\Program Files\Java\j2re1.4.2_08\bin\java.exe" -cp D:\JavaDevelopment;.;acm.jar EulerProblem10

prime: i=2
prime: i=3
prime: i=5
prime: i=7
prime: i=11
prime: i=13
prime: i=17
prime: i=19
The sum of the primes up to two million is 77

And with a current version:
Running: D:\Java\jdk1.6.0_25\jre\bin\java.exe -Xmx512M -classpath D:\JavaDevelopment;. EulerProblem10

prime: i=2
prime: i=3
prime: i=5
prime: i=7
prime: i=11
prime: i=13
prime: i=17
prime: i=19
The sum of the primes up to two million is 77

0 error(s)

I can't believe you can get all good numbers with the existing code.

Edited 5 Years Ago by NormR1: n/a

Yup - here's my 1st hundred primes...(sorry - all my primes up to 100)
Prime: 2
Prime: 3
Prime: 5
Prime: 7
Prime: 11
Prime: 13
Prime: 17
Prime: 19
Prime: 23
Prime: 29
Prime: 31
Prime: 37
Prime: 41
Prime: 43
Prime: 47
Prime: 53
Prime: 59
Prime: 61
Prime: 67
Prime: 71
Prime: 73
Prime: 79
Prime: 83
Prime: 89
Prime: 97
The sum of the primes up to two million is 142,917,828,921
(ignoring any debates about whether 1 is a prime).

I just changed Total to long and added/updated the print statements to this:

public ProblemTen() {
      boolean Primes[] = Erasthones(2000000);
      long Total = 0;
      for (int i = 2; i < Primes.length; i++) {
         if (!Primes[i]) {
            if (i < 100) System.out.println("Prime: " + i);
            Total += i;
         }
      }
      System.out.println("The sum of the primes up to two million is " + 
            new DecimalFormat ("#,###").format(Total));
   }

Edited 5 Years Ago by JamesCherrill: not 1st hundred but all primes &lt;= 100, sorry.

Change to this:
boolean Primes[] = Erasthones(20);
and look at the last two values printed out.

Prime: 2
Prime: 3
Prime: 5
Prime: 7
Prime: 11
Prime: 13
Prime: 17
Prime: 19
Prime: 20
The sum of the primes...

Interesting, I'll look closer...

OK, I found some problems with the main sieve loop - most notably that it was not processing the last element of the array. I also pruned out some redundant iterations, and a redundant if test, so now it looks like this:

public static boolean[] Erasthones(int ToWhat) {
      boolean Seive[] = new boolean[ToWhat + 1];

      int PrimeAt = 2;
      int Multiplier = 2;

      while (PrimeAt <= ToWhat/2) {  // no point trying larger values (*2)
         while ((Multiplier * PrimeAt) <= ToWhat) { // not ToWhat -1
            Seive[Multiplier * PrimeAt] = true;
            Multiplier++;
         }

         Multiplier = 2;

         for (int i = PrimeAt + 1; i < Seive.length; i++) {
            if (Seive[i] == false) {
               PrimeAt = i;
               break;
            }
         }

        // if (PrimeAt >= ToWhat) { // redundant
        //   break;
        // }

      return Seive;
   }
      }

Looks better for the 20 case, and doesn't break the 2,000,000 so how's that for you?

Edited 5 Years Ago by JamesCherrill: n/a

Soory - here's clean version...

class ProblemTen {

   public ProblemTen() {
      
      boolean Primes[] = Erasthones(2000000);
      long Total = 0;
      for (int i = 2; i < Primes.length; i++) {
         if (!Primes[i]) {
            if (i < 101) System.out.println("Prime: " + i);
            Total += i;
         }
      }
      System.out.println("The sum of the primes up to two million is "
            + new DecimalFormat("#,###").format(Total));
   }

   public boolean[] Erasthones(int ToWhat) {
      boolean Seive[] = new boolean[ToWhat + 1];

      int PrimeAt = 2;

      while (PrimeAt <= ToWhat / 2) { // no point trying larger values (*2)
         int Multiplier = 2;
         while ((Multiplier * PrimeAt) <= ToWhat) { // not ToWhat -1
            Seive[Multiplier * PrimeAt] = true;
            Multiplier++;
         }

         for (int i = PrimeAt + 1; i < Seive.length; i++) {
            // assumes there will always be at least one prime 
            // in the second half of the range...
            if (Seive[i] == false) {
               PrimeAt = i;
               break;
            }
         }

      }

      return Seive;
   }
}

So now where is the OP's thinking that the code worked differently in the debugger?
I can't imagine his tracing for 2000000 times.

Question about the debugger: Does it have conditional breaks?
For example: break here when X > 19999900

My only guess is that the debugger may handle the int overflow differently from the normal runtime - the OP said all his problems went away when he changed Total to long.

I think we have spoiled it now for an opportunity for the OP to learn how to debug.
Obviously long vs int did not make the algorithm produce good results for the last few values.
He mis-interpreted the code working for a few cases as working for all cases.

No one has yet posted the correct answer. I get: 142,913,828,922

Edited 5 Years Ago by NormR1: n/a

Sorry I can't find anything labelled: 1:44 pm

Is this what you refer to: Is the correct answer 142917828921?
Quite different from whatI get: 142,913,828,922

That was with the 19999999 and 20000000 added in.

Edited 5 Years Ago by NormR1: n/a

I get 142,913,828,922 also. The earlier value was from a web site, but I didn't worry about it too much apart from seeing that it was > max int.
ps A normal listing doesn't show the time, but if you "go advanced" it puts the posts in reverse order and shows the time. No idea why.

Edited 5 Years Ago by JamesCherrill: n/a

OK, final answer... Wolfram agrees the sum of the primes up to 2000000 is 142,913,828,922. See attached screen shot
J

Attachments Wolframs_answer.JPG 35.94 KB
This question has already been answered. Start a new discussion instead.