シクシク素数列 Advent Calendar 2018 C#編

「シクシク素数列 Advent Calendar 2018」の16日目の記事になります。問題詳細は当該アドベントカレンダーのページを参照していただくとして、ごく簡単にまとめておくと「100以下の自然数nが与えられたとき、n番目までの"シクシク素数"を求めて、カンマ区切りで出力しなさい」というものになります。なお"シクシク素数"とは数値として4または9を含む素数を指します。

本記事ではこの"シクシク素数"問題をC#で解答しています。解答コードは次の通りです。

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

namespace Prime4949
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 100;
            var answer = string.Join(",", Primes().Where(Program.HasFourOrNine).Take(n));
            Console.WriteLine(answer);
        }

        /// <summary>
        /// 数値に4か9を含むかどうかを判定する。
        /// </summary>
        /// <param name="x">自然数</param>
        /// <returns>xが4か9を含む場合true</returns>
        static bool HasFourOrNine(int x)
        {
            while (x > 0)
            {
                int mod = x % 10;
                if (mod == 4 || mod == 9)
                {
                    return true;
                }
                x /= 10;
            }
            return false;
        }

        /// <summary>
        /// 素数を次々に生成する。
        /// 
        /// 注意: 
        ///     任意の素数をxとすると、x+1..x^2に1つ以上の素数が含まれていることを前提にしています。
        ///     そのほか、説明のためにもろもろの検査をすっ飛ばしています。
        ///     クリティカルな場面では利用しないことをおすすめします。
        /// </summary>
        /// <returns>素数</returns>
        static IEnumerable<int> Primes()
        {
            var primes = new List<int> { 2, 3, 5 };
            for (int index = 0; ; index++)
            {
                if (index == primes.Count)
                {
                    var min = primes.Last() + 1;
                    var max = min * min;
                    var integers = Enumerable.Range(min, max - min + 1).ToList();
                    foreach (var prime in primes)
                    {
                        int sieving = integers.FindIndex(digit => digit % prime == 0);
                        while (sieving < integers.Count)
                        {
                            integers[sieving] = -1;
                            sieving += prime;
                        }
                    }
                    primes.AddRange(integers.Where(integer => integer != -1));
                }

                yield return primes[index];
            }
        }
    }
}

---

シンプルな問題なので解答方法はいろいろあると思いますが、今回は次のような方針を採用してみます:「素数列から4949性を満たすものをフィルタリングする」。まず素数列の生成ですが、今回はいわゆるエラトステネスのふるいを利用することにしました。エラトステネスのふるいは素数判定法のひとつで、指定された整数以下の素数を単純かつ効率的に求めることができ、プログラミングの教材にもよく利用されます。「指定された整数以下の素数を求める」という記述を見ると、今回のように「無限に素数を作りたい」という要件にマッチしないようにも思えますが、工夫次第ではなんとでもなり、それを実装したものがPrimesメソッドになります。

4949性を満たすかどうか--すなわち与えられた整数が数値として4または9を含むかの判定を行っているのがメソッドHasFourOrNineで、除法をうまく利用して整数xを各桁ごとにばらしています。