4
\$\begingroup\$

I have been attempting the questions at Project Euler and I am trying to find the sum of Primes under two million (question 10)

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 attempt which does work, but I would like to know if there is any way to improve this code. Any suggestions welcomed!

class SumOfPrimes
{
    static void Main(string[] args)
    {
        Primes primes = new Primes(2000000);
        long sum = 0;
        foreach(int p in primes.list_of_primes){
            sum += p;
        }
        Console.WriteLine(sum);
        Console.ReadLine();
    }
}

class Primes
{
    public HashSet<int> all_numbers = new HashSet<int>();
    public HashSet<int> list_of_primes = new HashSet<int>();
    public HashSet<int> list_of_nonprimes = new HashSet<int>();

    public Primes(int n)
    {
        all_numbers = new HashSet<int>(Enumerable.Range(1, n));
        for (int i = 2; i < Math.Sqrt(n) + 1; i++)
        {
            for (int j = 3; j <= n / i; j++)
                list_of_nonprimes.Add(i * j);
        }
        list_of_primes = new HashSet<int>(all_numbers.Except(list_of_nonprimes));
    }
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ just want to let you know - after you solve your project euler question . you can see the problem list and a PDF document in general a link to PDF document explains the best way to do the problem. \$\endgroup\$
    – aked
    Apr 18 '13 at 14:37
  • \$\begingroup\$ Yes I know but they are more interested in the mathematical methods whereas I am looking for specific feedback on code optimisation and efficiency, a topic not covered there at all. \$\endgroup\$
    – phcoding
    Apr 18 '13 at 14:39
  • \$\begingroup\$ Math.Sqrt(n) and n/i in the for loop should be made local variables instead so it got calculated once. Now it got executed unnecessarily in every single iteration. \$\endgroup\$
    – tia
    Apr 23 '13 at 5:34
2
\$\begingroup\$

Some other things that you can try, short of trying a totally different algorithm:

  • rename all_numbers to prime_candidates and remove composite numbers from it. (list_of_nonprimes.Add(i * j); -> prime_candidates.Remove(i*j). Avoiding the Except at the end.

  • You can also hold which numbers are non primes in an array of bools and lose all the HashSets. Changing:

    list_of_nonprimes.Add(i * j)
    

    to

    nonprimes[i*j] = true;
    

    Thus avoiding a bunch of hash lookups. After the loops sum up any n s.t. nonprime[n]==false

  • You can also use a BitArray instead of a bool array. Because it is more space efficient it might reduce cache misses.

Of course, you can only be sure if any of these actually makes any improvement after you try.

\$\endgroup\$
1
\$\begingroup\$

One slight improvement you can do is

All Prime numbers could be represented this format

2,3,4,5 and

6,7,8,9,10,11 or 12,13,14,15,16,17 or 18,19,20,21,22,23

6k,6K+1 ,6k+2,6K+3,6k+4,6k+5

so only prime number possible is

6k+1 and 6k+5

So you can step your for loop by 6

this is copied form Wikipedia http://en.wikipedia.org/wiki/Primality_test

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as testing all m.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the suggestion this is a good point. However, this idea is implicit in the code I have used above. As a sieve is used, in the first step and second step all multiples of 2 and 3 are added to the list of non-primes. This is equivalent to the idea of removing all numbers of the form 6k+2,6k+3,6k+4 and 6k. \$\endgroup\$
    – phcoding
    Apr 18 '13 at 14:41
1
\$\begingroup\$

If you implement @abuzittin gillifirca's suggestion of preparing the known prime candidate list as you go, another important improvement at an algorithm level would be to only sieve on primes or prime candidates. When you are looping i and j for applying the sieve, it is redundant to check for composite multiples (like 6), because those numbers would already have been sieved out by smaller i or j.

In other words, instead of looping 1 by 1 for values of i and j, loop through the contents of known prime candidates for both and you will skip a lot of unnecessary sieve checks. This should also make your process exponentially faster for large primes because larger and larger primes are further and further apart, so you are saving more wasted time in checking composite multiples.

\$\endgroup\$
0
\$\begingroup\$

I'll focus on making loop quicker.

int ilimit = Math.Sqrt(n) + 1;
for (int i = 2; i < ilimit; i++)
{
    int jlimit = n / i
    for (int j = 3, sum = i * 3; j <= jlimit; j++) {
        list_of_nonprimes.Add(sum);
        sum += i;
    }
}

I made the loop ending expression more efficient, and replaced i*j with addition ,which is cheaper. The list_of_nonprimes should be modified accordingly to the accepted answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.