ProjectEulerを斬る！問3

Problem 3
02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195の素因数は5，7，13，29です。
600851475143の最も大きい素因数はいくつでしょうか。
(日本語訳：PNN)

a = 600851475143
l = 0
repeat sqrt(a) - 1
b = cnt + 2
if int(a/b)*b == a {
a = a/b
l = b
if a == 1 : break
}
loop

input l

出力結果：・・・・0
HSPの変数型では600851475143はあまりにも大きすぎるみたいです。

困りましたね・・・
じゃあ、C#で解くことにしましょう！

/*
Problem 3
02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
*/

using System;
namespace p
{
class kaiho
{
static void Main()
{
double a = 600851475143;
double b = a;
double l = 0;

//Console.WriteLine(Math.Sqrt(a));
for (double i = 2; i < Math.Ceiling(Math.Sqrt(b)); i++)
{
if (Math.Floor(a / i) == Math.Ceiling(a / i))
{
a = a / i;
if (a == 1)
{
l = i;
break;
}
}
}
Console.WriteLine(l);
Console.ReadKey();
}
}
}

出力結果：6857

for (double i = 2; i < Math.Ceiling(Math.Sqrt(b)); i++)
これは素数判定でよく使うテクニックですね。ある数の素因数は、その平方根より大きくなることはないという性質を利用したものです。今回の解答には必要ありませんが、一応テクニックとして紹介しておきます。