Problem58 螺旋素数

問題

1から始めて, 以下のように反時計回りに数字を並べていくと,
辺の長さが7の渦巻きが形成される

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

面白いことに, 奇平方数が右下の対角線上に出現する.
もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である.
ここで割合は8/13 = 62%である.

渦巻きに新しい層を付け加えよう.すると辺の長さが9の渦巻きが出来る.
以下, この操作を繰り返していく.
対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static bool IsSosuu(int pVal)
    {
        if (pVal == 1) return false;
        if (pVal == 2) return true;
        if (pVal % 2 == 0) return false;
        for (int I = 3; I * I <= pVal; I += 2) {
            if (pVal % I == 0) return false;
        }
        return true;
    }

    static void Main()
    {
        int TotalCnt = 0;
        int TotalSosuuCnt = 0;

        double SosuuRate;
        int N = 1;
        while (true) {
            List<int> TaikakusenList = DeriveTaikakusenList(N);

            TotalCnt += TaikakusenList.Count;
            TotalSosuuCnt += TaikakusenList.Count(A => IsSosuu(A));

            SosuuRate = (double)TotalSosuuCnt / (double)TotalCnt;
            Console.WriteLine("HenLen={0},Cnt={1},SosuuCnt={2},Rate={3}",
                2 * N - 1, TotalCnt, TotalSosuuCnt, SosuuRate);
            if (2 * N - 1 >= 9 && SosuuRate < 0.1D) { //問題文により辺の長さは9以上
                Console.WriteLine("対角線上の素数の割合が10%未満になりました");
                return;
            }
            N++;
        };
    }

    static List<int> DeriveTaikakusenList(int pN)
    {
        if (pN == 1) return new List<int>() { 1 };

        int CurrHenLength = 2 * pN - 1;
        int PrevHenLength = CurrHenLength - 2;

        int PrevVal = PrevHenLength * PrevHenLength;
        var WillReturnList = new List<int>();
        for (int I = 1; I <= 4; I++)
            WillReturnList.Add(PrevVal + (CurrHenLength - 1) * I);
        return WillReturnList;
    }
}

実行結果

HenLen=26229,Cnt=52457,SosuuCnt=5247,Rate=0.100024782202566
HenLen=26231,Cnt=52461,SosuuCnt=5247,Rate=0.100017155601304
HenLen=26233,Cnt=52465,SosuuCnt=5248,Rate=0.100028590488897
HenLen=26235,Cnt=52469,SosuuCnt=5248,Rate=0.100020964760144
HenLen=26237,Cnt=52473,SosuuCnt=5248,Rate=0.100013340194005
HenLen=26239,Cnt=52477,SosuuCnt=5248,Rate=0.100005716790213
HenLen=26241,Cnt=52481,SosuuCnt=5248,Rate=0.0999980945485033
対角線上の素数の割合が10%未満になりました

解説

エラトステネスの篩ではなく、試し割りで素数かを判定してます。