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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
sv011
0 / 0 / 0
Регистрация: 09.11.2012
Сообщений: 25
17.11.2012, 22:42     Найти наибольший общий делитель двух чисел #1
Задача "Длинный НОД" Даны два числа. Найти их наибольший общий делитель. Входные данные Вводятся два натуральных числа, не превышающих 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;               
}
я так поняла, что нужно его оптимизировать, уменьшить время работы...но как это сделать без введения функций?)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2012, 22:42     Найти наибольший общий делитель двух чисел
Посмотрите здесь:

C++ Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел.
Требуется найти наибольший общий делитель двух чисел Фибоначчи. C++
Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел C++
C++ Найти наибольший общий делитель двух чисел используя алгоритм Евклида
Найти наибольший общий делитель двух чисел C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
JlightenDev_C++
 Аватар для JlightenDev_C++
61 / 61 / 7
Регистрация: 12.08.2012
Сообщений: 150
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;               
}
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 23:01     Найти наибольший общий делитель двух чисел #3
http://ru.wikipedia.org/wiki/Бинарны...нахождения_НОД
sv011
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
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 23:15     Найти наибольший общий делитель двух чисел #5
sv011, перепишите алгоритм согласно ссылке, которую я вам кинул
Andrey1945
0 / 0 / 0
Регистрация: 21.09.2015
Сообщений: 39
25.10.2015, 19:02     Найти наибольший общий делитель двух чисел #6
Помогите пожалуйста такой код под java сделать.
Yandex
Объявления
25.10.2015, 19:02     Найти наибольший общий делитель двух чисел
Ответ Создать тему
Опции темы

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