Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
coby9
0 / 0 / 0
Регистрация: 21.04.2014
Сообщений: 3
23.04.2014, 17:40     Вычислить наименьшее общее кратное всех целых чисел от 1 до n #1
Есть 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);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2014, 17:40     Вычислить наименьшее общее кратное всех целых чисел от 1 до n
Посмотрите здесь:

Найти наименьшее общее кратное (НОК) натуральных чисел С++ C++
[C++ ] Найти наименьшее общее кратное трех чисел C++
Найти наименьшее общее кратное (НОК) n натуральных чисел C++
C++ Наименьшее общее кратное трёх чисел
C++ Даны натуральные числа X и Y. Вычислить их наименьшее общее кратное.
C++ Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B
C++ Написать программу, вычисляющую НОК (наименьшее общее кратное) двух целых чисел
Вычислить наименьшее общее кратное двух натуральных чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 14:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru