素数

演算、出力とも1秒くらいでした。
馬鹿正直にエラトステネスのふるいを実行…どう考えても奇数だけ処理した方が早いでしょう。

using System;
using System.IO;

namespace PN1 {
	class Program {
		const int MAX = 10000000;
		static readonly double SQRTMAX = Math.Sqrt(MAX);
		static readonly double TPS = TimeSpan.TicksPerSecond;
		static bool[] p;
		static void Main(string[] args) {
			var t0 = DateTime.Now.Ticks;
			p = new bool[MAX];//初期化
			p[0] = true;//1は素数でない
			for (int i = 1; SQRTMAX > i; i++) {
				if (!p[i - 1]) {//素数ならば
					for (int j = i * 2; MAX > j; j += i) {
						p[j - 1] = true;//倍数は非素数にする
					}
				}
			}
			var t1 = DateTime.Now.Ticks;
			using (var sw = new StreamWriter("PN1.txt")) {
				for (int i = 1; MAX > i; i++) {
					if (!p[i - 1]) {
						sw.WriteLine(i);
					}
				}
			}
			var t2 = DateTime.Now.Ticks;
			Console.WriteLine((t1 - t0) / TPS);
			Console.WriteLine((t2 - t1) / TPS);
		}
	}
}