Pongeponge

Project Euler : Problem 47 『Distinct primes factors』

因数分解 (Aクラスブックス)


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

 要は順番に素因数分解していって素因数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();
        }
    }
}


 実行時間が約25秒から約1.5秒に縮まりましたとさ。



因数分解 (Aクラスブックス)

因数分解 (Aクラスブックス)

  • 作者:成川 康男
  • 出版社/メーカー: 昇龍堂出版
  • 発売日: 2014/10/01
  • メディア: 単行本
東大の先生!  文系の私に超わかりやすく数学を教えてください!

東大の先生! 文系の私に超わかりやすく数学を教えてください!

  • 作者:西成 活裕
  • 出版社/メーカー: かんき出版
  • 発売日: 2019/01/21
  • メディア: 単行本
因数分解 - 入学から卒業まで

因数分解 - 入学から卒業まで

  • 作者:金田 数正
  • 出版社/メーカー: 内田老鶴圃
  • 発売日: 1992/08
  • メディア: 単行本