0 / 0 / 0
Регистрация: 09.11.2012
Сообщений: 25
1

Найти наибольший общий делитель двух чисел

17.11.2012, 22:42. Показов 5356. Ответов 5
Метки нет (Все метки)

Задача "Длинный НОД" Даны два числа. Найти их наибольший общий делитель. Входные данные Вводятся два натуральных числа, не превышающих 10^9 (запись 10^9 обозначает "10 в 9-й степени", то есть 1000000000). Выходные данные Выведите НОД введенных чисел

мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>     
#include <cmath>        
using namespace std;    
int main(){
       int a,b,nod=1,d=1;
       cin>>a>>b;
       int x=a;
       if(b>a) x=b;
 
       for(int i=1;i<=x;i++){
           if(d>nod) nod=d;
           if(a%i==0 && b%i==0){
              d=i;}
       }
       cout<<nod;
                   
return 0;               
}
я так поняла, что нужно его оптимизировать, уменьшить время работы...но как это сделать без введения функций?)
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.11.2012, 22:42
Ответы с готовыми решениями:

Найти наибольший общий делитель двух чисел
Задание: найти наибольший общий делитель двух чисел. Сам код: #include &lt;iostream&gt; using...

Найти наибольший общий делитель двух чисел
найти наибольший общий делитель двух чисел с помощью рекурсии и без нее

Найти наибольший общий делитель двух чисел
Для заданных натуральных целых чисел n и m найти наибольший общий делитель (НОД), используя...

Найти наибольший общий делитель двух натуральных чисел
номер 2: Составьте программу определения наибольшего общего делителя двух натуральных чисел.

5
64 / 64 / 33
Регистрация: 12.08.2012
Сообщений: 151
17.11.2012, 22:58 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>                
int main(){
int a(0), b(0), d(1);
std::cin >> a >> b;
int x = a;
if(b > a){
x = b;
}
for(int i = 1; i <= x; i++){
        if(a%i == 0 && b%i == 0){
                  d = i;
                  }
        }
       std::cout << d;         
return 0;               
}
1
574 / 557 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 23:01 3
http://ru.wikipedia.org/wiki/Б... ждения_НОД
2
0 / 0 / 0
Регистрация: 09.11.2012
Сообщений: 25
17.11.2012, 23:12  [ТС] 4
Цитата Сообщение от JlightenDev_C++ Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>                
int main(){
int a(0), b(0), d(1);
std::cin >> a >> b;
int x = a;
if(b > a){
x = b;
}
for(int i = 1; i <= x; i++){
        if(a%i == 0 && b%i == 0){
                  d = i;
                  }
        }
       std::cout << d;         
return 0;               
}
все равно пишет Time-limit exceeded

Добавлено через 57 секунд
Time limit: 2000 ms
Memory limit: 256 M
0
574 / 557 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 23:15 5
sv011, перепишите алгоритм согласно ссылке, которую я вам кинул
1
0 / 0 / 0
Регистрация: 21.09.2015
Сообщений: 40
25.10.2015, 19:02 6
Помогите пожалуйста такой код под java сделать.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.10.2015, 19:02
Помогаю со студенческими работами здесь

Найти наибольший общий делитель двух чисел Фибоначчи
Последовательностью Фибоначчи называется последовательность чисел F0 = 0, F1 = 1, … , Fk = Fk-1 +...

Найти наибольший общий делитель двух целых чисел
Знаю что есть задачи на эту тему, но нужного для себя не нашла. Не могу сообразить как сделать...

Найти наибольший общий делитель двух введённых чисел
Здравствуйте. Такая проблема. Нужно выявить наибольший общий делитель двух введённых чисел....

Найти наибольший общий делитель двух чисел Фибоначчи
Добрый вечер, решаю задачу, ошибка на шестом тесте. Условии задачи: Последовательностью...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru