Original

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

Find the sum of all the primes below two million.

和訳

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem10 {
        public Problem10() {
            bool isPrime;
            int rooti;
            long sum = 2, chk=100000;
            List<int> table = new List<int>(1000000);
            Console.WriteLine(this.ToString());
            for (int i = 3; ; i += 2) {
                isPrime = true;
                rooti = (int)Math.Sqrt(i);
                for (int j = 0; j<rooti&&j<table.Count;j++ ) {
                    if (i % table[j] == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    table.Add(i);
                    sum += i;
                    if (i > chk) {
                        Console.WriteLine("> " + i + " @" + table.Count);
                        chk += 100000;
                    }
                    if (i > 2000000) {
                        sum -= i;
                        break;
                    }
                }
            }
            Console.WriteLine("> " + sum);
        }
    }
}


一度求めた素数はキャッシュしています。