オラ計画第5題

1716 ワード

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の手順は以下の通りです.
解:
#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; }