Problem3『Largest prime factor』

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)
        {
            //因数分解の場合ルートn以下の素数で十分なので
            double rn = (double)(int)Math.Sqrt(n);

            //ルートn以下の素数を取得
            List<int> pl = CreatePrimeList((int)rn);

            //nを割れる最も大きい素数を調べる
            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;
        }
    }
}