エラトステネスの篩
上の記事をみて、エラトステネスの篩を 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