Project Euler Question 10 help

[John Sing]

Hello everyone I am trying to create a program to answer question 10 on Project Euler which is

"The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million."

Here is my current code

public class ProblemTen{
 public static int primeMax = 2000000;
 public static void main(String args[]){
  long x = 3;
  long y;
  long sum = 2;
 
  while(x<primeMax)
  {
  for (y=2; y<x; y++)
   {if(x%y==0)
    break;
   }
  if(y==x)
   {sum+=y;
    x++;
   }
  x++;
  System.out.println(x);
  }
  System.out.println(sum);  
 }
}

right now my loop that runs 2,000,000 times seems to be a bit much for java to handle because it freezes around the 90,000 range. How can I improve my code and get it to work? Thanks.

[Carey Brown]

To compute a list of "small" primes, the Sieve of Eratosthenes algorithm is the fastest. Much much faster than X%Y.
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Now, whether or not there is an algorithm that would specifically speed up the Euler calculation I don't know.

[Brian Smither]

(Not having looked at the project, nor any of the similar threads, nor aware of any other proven algorithm) There are some prima facie assumptions we can make about prime numbers.

Other than 2, they are all odd. So, no sense testing each and every number up to 2M. Give some thought to skipping over even numbers. Then, give some thought to never testing x%2.

(If you have learned about arrays) You may want to make some small scale experiments - the limit being 10K, for example - to observe that for any modulo of zero, the operands can never be a number already shown to be not prime. That is, in the 2,3,5,7,11,13 sequence, the next test is for 15. So, no sense testing 15%4 because 4 has already been discarded as not prime, being a multiple of 2.

Then, 15%5 is zero and we discard 15. Any number discarded is known to be a multiple of an even lower number.

Then, 17. Working through an array of known primes, we find no solution. Same for 19.

Then, 21. Working through an array of known primes, we find 3 as a solution, so discard 21.

How about 323? Testing 323%17 is a solution, so discard it. The point here is that the inner loop only went seven iterations instead of seventeen.

[Carey Brown]

Dusted off my old sieve program.
Milli-seconds to compute primes up to 2,000,000 : 20
There are 148,933 primes

[Campbell Ritchie]

It might not be as quick to compute as a Sieve of Eratosthenes, but you can use a Stream.

total = IntStream.inclusiveRange(2, 20_000_000).
                 .something(...)
                 .somethingElse(...)
                 .total();

I shall leave you to go through the IntStream documentation and find out how many of those methods actually exist. If you have a Sieve array ready, you can use it from one of those calls in the stream to find whether the number is prime. I haven't found any isPrime methods but there is an isProbablePrime method in the BigInteger class.

[Campbell Ritchie]

I got the same result using a Sieve and using the BigInteger method, but the BigInteger technique is much slower. I think the isProbablePrime method is slow.
It took about 1.1s to set up a Sieve with 20,000,000 elements, about 0.6s to use a Stream which interrogates the Sieve and 3½min using isProbabePrime. My current computer is very slow at times.

[Carey Brown]

It's 2,000,000 not 20,000,000
I used a BitSet instead of an array

[Campbell Ritchie]

I thought 144000 primes sounded rather too few. . . .

[Carey Brown]

With this code

import java.util.stream.LongStream;

public class TestStreams
{
	public static void main( String[] args )
	{
		long			start, stop;
		
		try
		{
			start = System.currentTimeMillis();
			Primes primes = new Primes( 2_000_000 );
			stop = System.currentTimeMillis();
			System.out.format("Fill sieve: %,d milli-seconds%n", stop-start );
			
			start = System.currentTimeMillis();
			long total = LongStream
				.range( 2, 2_000_000 )
				.filter( i -> primes.isPrime( (int)i ) )
				.sum();
			stop = System.currentTimeMillis();
			System.out.format("Filter LongStream: %,d milli-seconds%n", stop-start );
			
			System.out.format( "Total: %,d%n", total );
		}
		catch( Exception e )
		{
			e.printStackTrace();
		}
	}
}

I got this

Fill sieve: 20 milli-seconds
Filter LongStream: 60 milli-seconds
Total: 142,...

I was a bit surprised at how long the stream took.

[Winston Gutkowski]

John Sing wrote:right now my loop that runs 2,000,000 times seems to be a bit much for java to handle because it freezes around the 90,000 range. How can I improve my code and get it to work? Thanks.

OK, well first off, your line 10 check is extremely wasteful. You don't have to check all divisors from 2 to x or even close.

Second: You only need to check prime divisors, because if the divisor - y in your program - is composite (ie, not prime), and
  x % y == 0
then x must ALSO divide exactly by y's divisors. And since you're building up a list of primes anyway, why not just re-use it?

Third: As Carey suggested, it's probably worth making division by 2 a special case, since it eliminates so many "candidates" immediately.

HIH

Winston

[Piet Souris]

Gents,

pointing OP to the 'Sieve' is as far as I would go.

The whole point of Project Euler is to find out:
1) what exactly the problem is
2) then determining if brute force is applicable or not
3) having determined the method to use, how to implement it
4) optimizing comes only after solving it and seeing how fast all these Python guys/girls did it

So pleae don't give code.

[Winston Gutkowski]

Piet Souris wrote:pointing OP to the 'Sieve' is as far as I would go. ... So please don't give code.

I agree with you in general, but most of what Campbell and Carey were showing was specifically a Stream-oriented solution, which is specific to version 8.

TBH, I reckon that this is one thing that Streams probably aren't the best for - although I have to admit I rather like the idea of an open-ended PrimeStream class...

Winston

[Campbell Ritchie]

Winston Gutkowski wrote:. . . OK, well first off, your line 10 check is extremely wasteful. You don't have to check all divisors from 2 to x or even close.

The whole idea of Project Euler is to make people think about algorithms; you are supposed to find an efficient algorithm for finding prime numbers. Creating a sieve of Eratosthenes with an array or (good idea whoever said that) a BitSet is probably much faster than testing each number for primeness. Also remember you do not have to iterate the whole range, so your sieve creating algorithm doesn't run in quadratic time.

. . . You only need to check prime divisors, . . .

You do not need to check all of them. A little thought will allow you to reduce your search space greatly.

[Winston Gutkowski]

Campbell Ritchie wrote:The whole idea of Project Euler is to make people think about algorithms; you are supposed to find an efficient algorithm for finding prime numbers. Creating a sieve of Eratosthenes with an array or (good idea whoever said that) a BitSet is probably much faster than testing each number for primeness.

It seems to me that we're mixing up all sorts of things in this discussion:

1. The requirement - which is to return the sum of primes less than 2,000,000.

2. The algorithm - which presumably means the best one for getting ALL primes less than 2,000,000 - unless there is an alternative way of getting a sum which doesn't involve getting them all.

3. The implementation - which may or may not be best with a BitSet or any other data structure.

John asked us to critique his code which - and here I agree with Piet - we have signally failed to do.

Let's stick to the question.

Winston

[Carey Brown]

Winston Gutkowski wrote:John asked us to critique his code which - and here I agree with Piet - we have signally failed to do.

Yes, we've had a drunken weave off of the original post, but there were a number of optimizations suggested that would speed up the OP code incredibly. I went back to the OP code and massaged it with the suggestions plus one that was hinted at and I was able to get the sum in 240 milli-seconds, vs my 20 milli-seconds for the sieve (admittedly I have a fast machine).

To summarize the suggestions:

Treat '2' as a special case

Only process odd numbers

Only check numbers that were identified as primes previously

Hint: what's the maximum possible prime you need to check for any X?

[Winston Gutkowski]

Now here I am going to go off-topic, but simply to confirm how wonderful prime numbers are.

The maximum gap between two known primes so far discovered is 1,476 (between two 18 digit numbers) - and I'm sure it'll be beaten soon - but AFAIK we still don't even know how to calculate what the maximum gap is, let alone how to prove that two known primes are adjacent (beyond brute force).

The whole area seems to be riddled with conjecture - including Legendre's (which AFAIK has yet to be proven) - and yet we continue finding all sorts of "spirals" and patterns and other useful stuff while we're searching.

Good old Maths.

Winston

[Carey Brown]

Carey Brown wrote:

Hint: what's the maximum possible prime you need to check for any X?

I can't think of a way off hand to guide you to the hint without just coming out and saying it, but is much less than half of X.

A count of all tests without the hint: 499,998,500,001

A count of tests needed with the hint: 89,357,989