素数を求める(配列を使う練習)

エラトステネスのふるいで、素数を求めます。配列を使う練習。

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