Optimus Prime / inspiwrit projecteuler.net
私の環境とプログラムでは、答え出すまでに13秒くらいかかる。
問題
600851475143の素因数のうち、最も大きい値は何か。
考えた方法
とりあえず600851475143(長いので以下n)を因数分解すればいいのかな……?
と考えたので、
1. ルートnを求める
2. 2からルートnまでの素数リストを作る
3. nを割れるかどうか、素数リストを大きい方から調べる
4. 割れればそれが最大の素因数
こんな感じなりました。
素因数分解っぽいやつ(分解してない)
using System;
using System.Diagnostics;
namespace Problem3
{
class Program
{
static void Main(string[] args)
{
Debug.WriteLine(solv(600851475143));
}
static double solv(double n)
{
double rn = (double)(int)Math.Sqrt(n);
List<int> pl = CreatePrimeList((int)rn);
int max = 0;
for(int i = pl.Count-1; i >= 0; i--)
{
if (n % pl[i] == 0)
{
max = pl[i];
break;
}
}
return max;
}
static List<int> CreatePrimeList(int max)
{
List<int> pl = new List<int>();
pl.Add(2);
for (int i = 3; i <= max; i+=2)
{
if (isPrime(i, pl))
{
pl.Add(i);
}
}
return pl;
}
static bool isPrime(int n, List<int> pl)
{
foreach(int p in pl)
{
if (n % p == 0) return false;
}
return true;
}
}
}