Вычислить наименьшее общее кратное всех целых чисел от 1 до n

[coby9]

Есть 2 программы : (Вычислите наименьшее общее кратное всех целых чисел от 1 до n.
Входной файл содержит число n (1 ≤ n ≤ 1000).
Выведите целое число — ответ на задачу.) и (Найти наименьшее общее кратное набора из N целых чисел, лежащих в диапазоне от 1 до 1000. Под наименьшим общим кратным набора чисел понимается наименьшее из таких чисел, которые делятся на любое из чисел набора.Формат ввода
В первой строке задается количество чисел N (1 ≤ N ≤ 20) в наборе. Во второй строке перечисляются через пробел в любом порядке все N целых чисел набора.
Формат вывода
Вывести полученное наименьшее общее кратное для заданного набора чисел.)

Алгоритм в программах одинаковый, разница только со вводом данных! Реализовал поиск НОК обычном перебором в цикле, все работает, но программа превышает лимит времени! нужно реализовать с помощью разложения чисел на простые множители! Попытался реализовать http://math-prosto.ru/?page=pages/fi...k/find_nok.php второй способ! с помощью массивов, никак не могу добитья нужного результата, МБ кто подскажет! вот мой код:


int n,i,c,j,p,a,d,t,k;
main()
{scanf("%i",&n);
int A[n],B[n];
a=1;
for(i=0;i<n;i++)
{ A[i]=i+1;
//scanf("%d",&A[i]);
//if (a<A[i]) a=A[i];
}
a=n;
p=a;

//printf("%d",a);

d=2;
j=0;
while(d <=a)
{
if(a%d==0)
{ B[j]=d; //в массив В записываю простые множители наибольшего числа из исходного массива
a=a/d;
j++;
}
else
d=d+1;

}
t=1;
for (k=1;k<n-1;k++)
{
d=2;
i=0;
while(d <=A[k])
{
if(A[k]%d==0)
{
for (i=0;i<j-1;i++)
{ if (B[i]!=d)
{ t=d;
break;
}
if (B[i]==d) break;
}
A[k]=A[k]/d;
}

d=d+1;
p=p*t;
//printf("____%d",p);
t=1;
}
}

for(k=0;k<j;k++)
//printf("%d",B[k]);

printf("____%d",p);
}