Pongeponge

Project Euler : Problem 10 『Summation of primes』

Sieving FlourSieving Flour / peterjroberts
projecteuler.net


問題

 200万未満の素数の総和を求めよ。


エラトステネスの篩を使おうか

 素数のリストが欲しいわけだけど、
エラトステネスの篩*1で作ってみようと思う。


コード
using System;
using System.Diagnostics;

namespace Problem10
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(SumPrime());
        }

        /// <summary>
        /// 素数配列の総和を求める
        /// </summary>
        /// <returns>総和</returns>
        static Int64 SumPrime()
        {
            int[] p = SoE();

            Int64 sum = 0;
            for(int i = 0; i < p.Length; i++)
            {
                sum += p[i];
            }

            return sum;
        }

        /// <summary>
        /// エラトステネスの篩
        /// </summary>
        /// <returns>素数配列</returns>
        static int[] SoE()
        {
            int max = 2000000;
            int[] lp = new int[max-2];

            lp[0] = 2;
            for (int i = 1; i < lp.Length; i+=2)
            {
                lp[i] = 2+i;
            }

            int sq = (int)Math.Sqrt(max);
            for(int i = 1; i < sq; i++)
            {
                if (lp[i] != 0)
                {
                    for (int j = i + lp[i]; j < lp.Length; j += lp[i])
                    {
                        lp[j] = 0;
                    }
                }
            }

            return lp;
        }
    }
}
解答

 142913828922



ガーデン土ふるい 粗目 18cm

ガーデン土ふるい 粗目 18cm

国産桧丸フルイ 真中 40目 21cm 0.75mm目

国産桧丸フルイ 真中 40目 21cm 0.75mm目