Project Euler 10

Problem 10

• 配列の練習
• 答えは int だとオーバーフローする

using System;
using System.IO;
using System.Collections.Generic;

public class P010 {
    static List<int> sieve(int n) {
        bool[] xs = new bool[n+1];
        for (int i = 0; i <= n; i++) {
            xs[i] = true; // i を素数としてマーク
        }

        for (int i = 3; i <= n; i += 2) {
            if (xs[i]) { // 素数ならば
                int p = i + i;
                while (p <= n) {
                    xs[p] = false; // 素数マークを外す
                    p += i;
                }
            }
        }

        var primes = new List<int>();
        primes.Add(2);
        for (int i = 3; i <= n; i += 2) {
            if (xs[i]) {
                primes.Add(i);
            }
        }
        return primes;
    }

    public static void Main() {
        var primes = sieve(2000000);

        long ans = 0;
        foreach (int p in primes) {
            ans += p;
        }
        Console.WriteLine(ans);
    }
}