[Guitartripp]

Been a while since I posted here! After about a 2 year hiatus on programming, I've decided to take it back up with a vengeance! I've been devouring all I can this past couple of months, and loving every second!

I'm so happy that I stumbled upon Project Euler. It gives me many projects that I can sink my time into, allows me to learn more math (which I love), and has the added benefit of forcing me to optimize my code for speed.

I'm on problem number 10 now. Finding the sum of all primes below two million. Earlier problems involving primes were easy, and calculated pretty quickly, as the prime never really got too high. However.. two million..

So my question is, how can I optimize my code here? I'm using C#, by the way.

        static void Main(string[] args)
        {
            long prime = 2;
            long sum = 0;
            bool isPrime;


            do
            {
                isPrime = true;
                Console.WriteLine("Prime: {0} Sum: {1}", prime, sum);

                for (int i = 1; i < prime; i++)
                {
                    if (i == 1 || i == prime)
                        continue;
                    if (prime % i == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime)
                    sum += prime;

                prime++;
                Console.Clear();
            }
            while (prime <= 2000000);

            Console.WriteLine("Prime: {0} Sum: {1}", prime, sum);

            Console.ReadLine();

        }

I don't even know what else I could use to make it run faster..

It's currently been running for about.. 5-7 minutes now, and the prime number is only at ~630,000.

It's not a necessity, I would just like to know if it's possible, or if it's just going to take a bit no matter what because the limit is so high.

Thanks to anybody taking the time on this! Happy to be back =)

This post has been edited by Guitartripp: 16 August 2012 - 08:24 PM

[jon.kiparsky]

Keep a list of the primes as you find them, and use them to test instead of testing all of the composites.
Also, there's no need to test all of the possible divisors up to the number being tested. For any pair of numbers i,j such that i*j = n, either i or j must be less than or equal to what number? Figure that out and you'll cut your search space greatly.

[Curtis Rutland]

Here's an article I did a while back about a prime number iterator method:

http://www.dreaminco...terator-method/

I didn't focus on making it as efficient as possible, so there are obviously enhancements that can be made. But it's a good starting place.

[sepp2k]

The usual way to find all primes below a given number efficiently is to use a sieve like for example the Sieve of Eratosthenes.

[AdamSpeight2008]

Speaking of the Sieve approach,

  Public Function PrimesLessThan(Limit As Long) As IEnumerable(Of Long)
    Dim Sieve As Func(Of IEnumerable(Of Long), IEnumerable(Of Long)) =
      Function(Numbers As IEnumerable(Of Long))
        Dim First = Numbers.First()
        Dim NumbersLefts = (From Number In Numbers.Skip(1)
                            Where Not Number.IsDivisibleBy(First)).ToArray
        Return {First}.Concat(If(NumbersLefts.Any, Sieve(NumbersLefts), {}))
      End Function
    Return Sieve(N1(Limit).Skip(1))
  End Function

 Iterator Function N1(UpToValue As Integer) As IEnumerable(Of Long)
    For i = 1 To UpToValue - 1
      Yield i
    Next
  End Function

  <Extension()>
  Function IsDivisibleBy(n As Long, d As Long) As Boolean
    Return (n Mod d) = 0
  End Function

This post has been edited by AdamSpeight2008: 17 August 2012 - 09:41 AM

[TwoOfDiamonds]

One question : Using Sieve of Eratosthenes algorithm in this case you will have to allocate memory for 2 mil elements , right ?
I'm just learning C# so I'm not sure but I think there is a way to delete elements from a list / array / etc . (so you would delete non-prime elements and thus saving some memory)

If I'm wrong please correct me .

[sepp2k]

AdamSpeight2008, on 17 August 2012 - 06:04 PM, said:

Speaking of the Sieve approach,

That doesn't look like a proper sieve (or at least not a fast one). It looks like when you remove the multiples of a prime (First) from the sieve, you're actually going through all the numbers that are left in the sieve and check whether they're multiples of the First. That's a lot slower than iterating in steps of First.

I realize that the intent was to come up with a functional version of a sieve, but I don't think this will fare very well performance-wise compared to the Sieve of Eratosthenes.

TwoOfDiamonds, on 17 August 2012 - 07:15 PM, said:

One question : Using Sieve of Eratosthenes algorithm in this case you will have to allocate memory for 2 mil elements , right ?

Right.

Quote

I'm just learning C# so I'm not sure but I think there is a way to delete elements from a list / array / etc . (so you would delete non-prime elements and thus saving some memory)

You'd still have to allocate the complete list first before you'd start removing elements from it. So the initial memory consumption would be the same (and I'm not sure whether removing items from a list even frees any memory).

Also note that removing items from a list is an O(n) operation, so doing this would worsen the performance of the sieve drastically and kind of defeat the point of using the sieve in the first place.

If you want to cut down on the memory consumption, you can use a BitArray which would consume an 8th of the memory consumed by a boolean array (at some runtime cost - but significantly less than removing elements from a list would incur). That said a memory consumption of 2 megabytes isn't that bad, so I wouldn't bother.

[Skydiver]

No, you don't need to allocate memory for 2 million elements. It's just the graphical way that we are taught in school to show how the technique works where numbers are crossed off as we mark them as composite. As you've intuited, you can maintain lists.

Try going back to Project Euler problem #7 and instead of making a big array try the approach shown by AdamSpeight2008 above, or read about wheel factorization and only maintain lists of primes and the next possible primes.

This post has been edited by Skydiver: 17 August 2012 - 10:56 AM

[sepp2k]

Skydiver, on 17 August 2012 - 07:55 PM, said:

No, you don't need to allocate memory for 2 million elements.

To implement the Sieve of Eratosthenes you do.

[AdamSpeight2008]

sepp2k: It doesn't remove items from the list, but generate a new list contain all the non-multiples. I like that's really small. ~10LoC

It's still slows as a lazy snail's yawn.

[TwoOfDiamonds]

Is a list of 2 mil integers very demanding in terms of memory ? Or can a modern computer sustain that amount of required memory on the heap with no problem ?

EDIT: And instead of creating a new list , can't you change the non-prime elements to 0 since an assignment operation is faster than inserting a new item into a list . ( at least I think so )

@[user]Skydiver[/user] : could you please provide an example of this algorithm that will require less than 2 mil elements ? (wheel factorization doesn't count since it's a more advanced algorithm that only uses SoE as base) .

Thanks for you patience guys ! It seems that I can really learn lots of things on this forum !

This post has been edited by TwoOfDiamonds: 17 August 2012 - 01:40 PM

[AdamSpeight2008]

IEnumerable are read-only.

[TwoOfDiamonds]

Oh !
Like in foreach . Told you I'm new to C# . Doing my best to learn .
However, why can't you use fors or something like that that allows Reading and Writing ?

[Skydiver]

2 million integers is not 2MB. It is 2 million integers * 4 bytes per integer = 8MB.

Unfortunately, my pathetically slow solution to Project Euler problem #10 uses wheel factorization and just maintains lists of real primes and potential primes. The potential primes list has only the next ring outside the wheel as needed. As I said pathetically slow: 14 minutes to solve vs. using sieve that solves in about 200 milliseconds. But my objective was to learn how wheel factorization works, and not necessarily speed.

One of the simplest ways to not hold 2 million elements, is to realize right away that all even numbers are not prime. Then you instantly halve the 2 million elements that you need to store state to just 1 million. All the other potential primes will be some value (2i + 1) and can be stored in element i.

This post has been edited by Skydiver: 17 August 2012 - 02:06 PM

[sepp2k]

TwoOfDiamonds, on 17 August 2012 - 10:33 PM, said:

Is a list of 2 mil integers very demanding in terms of memory ? Or can a modern computer sustain that amount of required memory on the heap with no problem ?

For the Sieve of Eratosthenes you'd be using an array of two million booleans, not integers. That'd be two megabytes. That's not even close to a problematic amount of heap memory.

An array of two million integers, would take up eight megabytes, which is still not problematic.

Skydiver, on 17 August 2012 - 11:05 PM, said:

2 million integers is not 2MB. It is 2 million integers * 4 bytes per integer = 8MB.

Right, but no one said "integer" until the OP's most recent post (or if they did, I missed it).