オラ計画第5題
Problem 5:
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.
質問5:
2520は1〜10で割り切れる最小数である.
1から20で割り切れる最小の数を見つけます.
分析:
考え方1:小さいから大きいまでのサイクルで各数字をテストします.[利点:簡単で、時間が空間を変えて、数字を除去するのに適しています;欠点:効率が低い.]
構想2:a[1]~a[n]を1~nに等しくし、a[n]でa[1]~a[n-1]を除去する(除去できれば、各数を最大1回除去する)と、最小整数はa[1]*a[2]*から...a[n]が得られた.[利点:効率が高く、空間が時間を変える;
考え方2の手順は以下の通りです.
解:
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.
質問5:
2520は1〜10で割り切れる最小数である.
1から20で割り切れる最小の数を見つけます.
分析:
考え方1:小さいから大きいまでのサイクルで各数字をテストします.[利点:簡単で、時間が空間を変えて、数字を除去するのに適しています;欠点:効率が低い.]
構想2:a[1]~a[n]を1~nに等しくし、a[n]でa[1]~a[n-1]を除去する(除去できれば、各数を最大1回除去する)と、最小整数はa[1]*a[2]*から...a[n]が得られた.[利点:効率が高く、空間が時間を変える;
考え方2の手順は以下の通りです.
解:
#include <stdio.h>
#include <malloc.h>
#define PRINT printf
#define DPRINT printf
typedef int INT;
typedef char CHAR;
typedef void VOID;
INT MinDivNum(INT n) // [1~n]
{
if (n<1 || n>22)
return -1;
INT *a;
a = (INT *)malloc(sizeof(INT)*(n+1));
// a[1]~a[n] 1~n, a[n] a[1]~a[n-1]( , 1 )
//, a[1]*a[2]*...a[n]
INT i, j;
for (i=2; i<=n; i++)
{
a[i] = i;
for (j=2; j<i; j++)
{
if(0 == a[i] % a[j])
a[i] /= a[j];
}
}
INT nRes;
nRes = 1;
for (i=2; i<=n; i++)
nRes *= a[i];
free(a);
return nRes;
}
INT main(INT argc, CHAR *argv[])
{
INT n;
INT nRes;
while (1)
{
PRINT(" [1~22], :
");
scanf("%d", &n);
if (n < 0)
break;
nRes = MinDivNum(n);
PRINT(" 1 %d :
%d
", n, nRes);
}
return 0;
}