プロジェクトオイラー 問題5(project euler problem 5)
こんにちは!
Project EulerのProblem-5をC言語で解きました!
問題はこちら↓
<アルゴリズム>
・1~20までの素数のうち、20以下に収まる最大の数値になるまで素数の累乗を求めたものがあれば、20以下の数値をすべてカバーできる。
・これらをすべてかけたものが最小の解になる。
・処理時間がかなり短いため、for文による冗長な処理時間の平均をとる
<ソースコード>
/* 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? */ #include <stdio.h> #include <time.h> #define LOOP 100000 int main(void){ // 素数の累乗で、20以下に収まる最大のものをかけていけば、1~20で和り切れるようにカバーできる。 int ans = 1; int tmp; int Primenumber[8] = {2, 3, 5, 7, 11, 13, 17, 19}; int soinsuu[8]; clock_t start, end; start = clock(); for(int count = 1; count <= LOOP; count++){ ans = 1; for(int i = 0; i < 8; i++){ soinsuu[i] = Primenumber[i]; while(1){ tmp = Primenumber[i]; if(soinsuu[i] * tmp <= 20) soinsuu[i] = soinsuu[i] * tmp; else break; } ans *= soinsuu[i]; } } end = clock(); printf("Ans = %d\n", ans); printf("計測時間%lf[sec]\n", (double)(end - start) / CLOCKS_PER_SEC / LOOP); return 0; }
<実行結果>
Ans = 232792560 計測時間0.000000[sec]
これはかなり早いですね。