どーも、みつおです。
問題
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
出典:Problem5
解答
using System; using System.Collections.Generic; using System.Linq; namespace Problem5 { class Program { static void Main(string[] args) { Console.WriteLine(Solve()); Console.ReadLine(); } private static long Solve() { long ret = 0; int No = 20; List<int> soinsubunkailist = new List<int>(); //20から1ずつ減らすループ for (int i = No; 1 <= i; i--) { //iを素因数分解(すでに素因数分解のリストに値がある場合は追加しない) var soinsubunkai = YetData(i, soinsubunkailist); foreach (var tmp in soinsubunkai) { //素因数分解のリストに追加 soinsubunkailist.Add(tmp); } } //1~20の素因数分解(重複削除)の積 ret = soinsubunkailist.Aggregate((now, next) => now * next); return ret; } public static List<int> YetData(int n, List<int> data) { List<int> ret = new List<int>(); List<int> tmp = new List<int>(data); //nを素因数分解 var soinsu = SoinsuBunkai(n); foreach (var num in soinsu) { //素因数分解のリストにある場合、 if (!tmp.Remove(num)) ret.Add(num); } return ret; } public static IEnumerable<int> SoinsuBunkai(int n) { int i = 2; int tmp = n; //合成数xはp≤√xを満たす素因子pをもつという性質を利用 while (i * i <= n) { //iで割り切れるか判定 if (tmp % i == 0) { tmp /= i; yield return i; } else i++; } if (tmp != 1) yield return tmp; } } }
出力
232792560
コメント