Project Euler : Problem 47 『Distinct primes factors』

問題

projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047

力技で解こうぜ(ガンガンいこうぜ風に)

　要は順番に素因数分解していって素因数4種が4回連続すればいい。
ただ、最小の素因数4種の数は2×3×5×7の210なのでスタートをそこからに設定する。

ハッキリ言って遅い

　結果が出るまでに25秒くらいかかる。多分もっと効率のいい方法があるはず。
例えば、素数リストを先に作って使うだけでだいぶ早くなりそうではある。

コード

using System;

namespace ProjectEuler.Problem47
{
    class Program
    {
        static void Main()
        {
            var number = 2 * 3 * 5 * 7;

            for (int i = number; i < int.MaxValue; i++)
            {
                if (TrialDivision(i) == true)
                {
                    if (TrialDivision(i + 3) == true)
                    {
                        if (TrialDivision(i + 1) == true)
                        {
                            if (TrialDivision(i + 2) == true)
                            {
                                Console.WriteLine(i);
                                return;
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 試し割り法による素因数分解
        /// </summary>
        /// <param name="n">素因数分解する数</param>
        /// <returns>素因数が4種類ならtrue,それ以外はfalse</returns>
        static bool TrialDivision(int n)
        {
            //最大の除数
            int maxDiv = n / 2;
            //素因数のカウント
            int primeCount = 0;

            for (int i = 2; i <= maxDiv; i++)
            {
                bool findPrime = false;
                while (n % i == 0)
                {
                    n /= i;
                    findPrime = true;
                }

                if (findPrime == true) primeCount++;

                //4種類以上の素因数が見つかれば失敗
                if (primeCount > 4) return false;
            }

            if (primeCount == 4) return true;
            else return false;

        }
    }
}

答え

134043

　案外小さい数だった

エラトステネスの篩追加版

　気になったので追加版を作ってみた。

using System;
using System.Linq;

namespace ProjectEuler.Problem47
{
    class Program
    {
        static int[] Primes;

        static void Main()
        {
            Primes = ES(10000);

            var number = 2 * 3 * 5 * 7;

            for (int i = number; i < int.MaxValue; i++)
            {
                if (TrialDivision(i) == true)
                {
                    if (TrialDivision(i + 3) == true)
                    {
                        if (TrialDivision(i + 1) == true)
                        {
                            if (TrialDivision(i + 2) == true)
                            {
                                Console.WriteLine(i);
                                return;
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 試し割り法による素因数分解
        /// </summary>
        /// <param name="n">素因数分解する数</param>
        /// <returns>素因数が4種類ならtrue,それ以外はfalse</returns>
        static bool TrialDivision(int n)
        {
            //最大の除数
            int maxDiv = n / 2;
            //素因数のカウント
            int primeCount = 0;

            for (int i = 0; i < Primes.Length; i++)
            {
                bool findPrime = false;
                while (n % Primes[i] == 0)
                {
                    n /= Primes[i];
                    findPrime = true;
                }

                if (findPrime == true) primeCount++;

                //4種類以上の素因数が見つかれば失敗
                if (primeCount > 4) return false;
            }

            if (primeCount == 4) return true;
            else return false;

        }

        //エラトステネスの篩
        static int[] ES(int max)
        {
            int[] ps = new int[max + 1];

            for (int i = 0; i < ps.Length; i++)
            {
                ps[i] = i;
            }
            ps[1] = 0;

            for (int i = 2; i < ps.Length; i++)
            {
                for (int j = i; j < ps.Length; j++)
                {
                    if (ps[i] != 0) break;
                }

                for (int j = 2 * i; j < ps.Length; j += i)
                {
                    ps[j] = 0;
                }
            }

            return ps.Where(x => x > 0).ToArray();
        }
    }
}