エラトステネスの篩

haskell.g.hatena.ne.jp

上の記事をみて、エラトステネスの篩を C# で書いてみました。

// 2, 3, 4, 5, ...
static IEnumerable<int> Nums()
{
    int n = 2;
    while (true)
        yield return n++;
}

static Func<int, bool> MakePrimeFilter(int prime, Func<int, bool> isPrime)
{
    // x はこれまで登場した素数で割りきれない、かつ prime でも割り切れないならば、x は素数である
    return x => isPrime(x) && x % prime != 0;
}

static IEnumerable<int> Primes()
{
    Func<int, bool> isPrime = n => true;
    foreach (var x in Nums())
    {
        if (isPrime(x))
        {
            yield return x;
            isPrime = MakePrimeFilter(x, isPrime);
        }
    }
}

お試しコード。

public static void Main(string[] args)
{
    Console.WriteLine(string.Join(", ", Primes().Take(10)));    
    // => 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

    Console.WriteLine(Primes().ElementAt(1000)); // 7927
    
    // 10,000 より大きな最小の素数は?
    Console.WriteLine(Primes().SkipWhile(e => e <= 10000).First()); // 10007
}

※ このコードは効率はよくありません。関数を重ねるコードの書き方の練習用です。

双子素数も求めてみます。

// 双子素数を求める
static IEnumerable<Tuple<int, int>> Twins()
{
    foreach (var pair in Primes().Zip(Primes().Skip(1), (a, b) => Tuple.Create(a, b)))
    {
        if (pair.Item1 + 2 == pair.Item2)
            yield return pair;
    }
}

public static void Main(string[] args)
{
    var ts = Twins().Take(10);
    Console.WriteLine(string.Join(", ", ts.Select(e => $"({e.Item1}, {e.Item2})")));
    // => (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109)
}

元コード:

twins = filter ((2==) . uncurry subtract) $ s zip tail primes

上の ((2==) . uncurry subtract) のところがよく分からなかったので分解してみます。

subtract は、subtract a b で b - a を計算します。

Prelude> :t subtract
subtract :: Num a => a -> a -> a
Prelude> subtract 1 5
4

uncurry は、uncurry (+) (a, b)(+) a b を計算します。

Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c
Prelude> uncurry (+) (1, 3)
4

(2==) は、2 と等しいかを判定する関数です。

Prelude> :t (2==)
(2==) :: (Num a, Eq a) => a -> Bool
Prelude> (2==) 2
True
Prelude> (2==) 3
False

よって、(2==) . uncurry subtract は、タプル (a, b) を受け取って substract a b すなわち b - a が 2 と等しいかを判定する関数、ということになります。

Prelude> a = (2==) . uncurry subtract
Prelude> :t a
a :: (Eq a, Num a) => (a, a) -> Bool
Prelude> a (1, 3)
True
Prelude> a (1, 4)
False