素数を求める(配列を使う練習)
エラトステネスのふるいで、素数を求めます。配列を使う練習。
using System; namespace Example { class MainClass { public static void sieve(int n) { bool[] primes = new bool[n+1]; for (int i = 2; i <= n; i++) primes[i] = true; for (int i = 2; i <= n; i++) { if (primes[i]) { for (int j = i*2; j <= n; j += i) { primes[j] = false; // j is not prime } } } for (int i = 2; i <= n; i++) { if (primes[i]) { Console.Write(" " + i); } } Console.WriteLine(); } public static void Main(string[] args) { sieve(100); } } }
実行結果です。
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97