ProjectEulerを斬る！問5

Problem 5
30 November 2001

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

2520は1から10の整数全てで割り切れる最小の数です。（つまり最小公倍数）
では1から20の整数全てで割り切れる最小の数は幾つでしょう。
��日本語訳PNN）

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/*
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
*/
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int a = 20;

//2-20までの素数表作成
int yousosu = 2;
bool b_sosu = true;
int[] sosu = new int[2];
sosu[0] = 2;
sosu[1] = 3;
for (int i = 5; i <= a; i += 2)
{
int k = 0;
for (int j = 1; j <= yousosu - 1; j++)
{
if ((int)(i / sosu[j]) * sosu[j] == i)
{
b_sosu = false;
}
k = j;
}
if (b_sosu != false)
{
for (int j = sosu[k]; j <= Math.Sqrt(a); j += 2)
{
if ((int)(i / j) * j == i)
{
b_sosu = false;
}
}
}
if (b_sosu == true)
{
sosu.CopyTo(sosu = new int[yousosu+1],0);
sosu[yousosu] = i;
yousosu++;
}
else
{
b_sosu = true;
}
}

/*きちんと素数配列が出来ているかの✔
for (int i = 0; i <= yousosu -1; i++)
{
Console.WriteLine(sosu[i]);
}
Console.ReadLine();
*/

//最小公倍数を求める
int[,] yakusu = new int[21,21];
for (int i = 2; i <= a; i++)
{
int b = i;
for (int j = 0; j <= yousosu - 1; j++)
{
for (int k = 0; k >= 0; k = k)
{
if ((int)(b / sosu[j]) * sosu[j] == b)
{
yakusu[i, j]++;
b = b / sosu[j];
}
else
{
break;
}
}
if (b == 1)
{
break;
}

}
}
/*きちんと分配出来てるか確認
for (int i = 2; i <= a; i++)
{
Console.Write(i.ToString() + " : ");
for (int j = 0; j <= yousosu - 1; j++)
{
Console.Write(yakusu[i, j].ToString() + ",");
}
Console.Write("\n");
}
Console.ReadLine();*/

int[] max = new int[yousosu];
for (int i = 0; i <= yousosu - 1; i++)
{
for (int j = 2; j <= a; j++)
{
if (yakusu[j, i] >= max[i])
{
max[i] = yakusu[j, i];
}
}
}
/*確認*/
int kekka = 1;
for (int i = 0; i <= yousosu-1; i++)
{
kekka = kekka * (int)Math.Pow(sosu[i],max[i]);
}
Console.WriteLine(kekka);
Console.ReadLine();
}
}
}

出力結果：232792560
まず最初に1から20までの素数表の作成をして、すると1から20までの数字は必ずその素数の乗数の積で表されます。最小公倍数は、その各々の素数の乗数の最も大きい物の積でありますからそれで計算しています。

次の画像を見てください。


つまり出力結果の232792560=2^4 * 3~2 * 5 * 7 * 11 * 13 * 17 * 19ということです。