ProjectEulerを斬る！問7

Problem 7
28 December 2001

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?

最初の６つの素数をリストアップしてみると2,3,5,7,11,13となり、6番目の素数は13であることがわかります。
では10001番目の素数はいくつでしょうか。

これは結構処理に時間が掛かりそうですから、余計な演算を出来る限るそぎとる感じで行きましょう。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int num = 2;
double prime = 0;
for (double i = 3; num <= 10001; i += 2)
{
bool b_prime = true;
for (double j = 3; j <= Math.Sqrt(i); j += 2)
{
if (Math.Floor(i / j) == Math.Ceiling(i / j))
{
b_prime = false;
break;
}
}
if (b_prime==true)
{
prime = i;
num ++;
}
}
Console.WriteLine(prime);
Console.ReadLine();
}
}
}

出力結果：104743

意外に時間はかからなかった。