ネタ元 → Rさんのふるい
素数を列挙しろ、と。
Rさんはエラトステネスのふるいを紹介してくれてますんで、
僕は素数表を再帰的に拡大する方法で。
n が素数か否かを調べるには√n 以下の素数全てで割ってみればわかります。
なので、n以下の素数表が欲しいときは、√n以下の素数表を用意してそいつ
を使って√nからnまでの素数を追加すればえぇです。
nまでの素数表は √nまでの素数表 を基に作れるわけね。
これを再帰的に適用すれば、
nまでの素数表は √nまでの素数表 を基に作れます。
√nまでの素数表は √√nまでの素数表 を基に作れます。
√√nまでの素数表は √√√nまでの素数表 を基に作れます。
…
やってみよぉやないのん。
using System;
using System.Collections.Generic;
public class Program {
// n以下の素数を列挙する
public static IEnumerable<int> make_primes(int n) {
// n <= 4 なら 素数は 2 と 3
if ( n <= 4 ) { yield return 2; yield return 3; }
else {
// √n 以下の素数をprimesに格納
List<int> primes =
new List<int>(make_primes((int)Math.Sqrt((double)n)));
// √n 以下の素数を列挙
foreach ( int prime in primes ) yield return prime;
// √n < i < n なる i のうち、素数であるものを列挙する
for ( int i = primes[primes.Count-1] + 2; i <= n; i += 2 ) {
// primes中にiを割り切るものがなかったとき、iは素数である。
bool has_divisor = false;
foreach ( int prime in primes ) {
if ( i % prime == 0 ) {
has_divisor = true;
break;
}
}
if ( !has_divisor ) yield return i;
}
}
}
public static void Main() {
foreach ( int prime in make_primes(100) ) {
Console.Write("{0} ", prime);
}
}
}