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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
sv011
0 / 0 / 0
Регистрация: 09.11.2012
Сообщений: 25
#1

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

17.11.2012, 22:42. Просмотров 2445. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2012, 22:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти наибольший общий делитель двух чисел (C++):

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

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

Найти наибольший общий делитель двух чисел - C++
Задание: найти наибольший общий делитель двух чисел. Сам код: #include &lt;iostream&gt; using namespace std; int main() { ...

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

Требуется найти наибольший общий делитель двух чисел Фибоначчи. - C++
ЗАДАЧА №384 Числа Фибоначчи - 3 (Время: 1 сек. Память: 16 Мб Сложность: 52%) Последовательностью Фибоначчи называется...

Найти наибольший общий делитель и наименьшее общее кратное двух чисел - C++
Даны два натуральных числа m и n. Найти их наибольший общий делитель и наименьшее общее кратное. Определить в программе собственную функцию...

5
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;               
}
1
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 23:01 #3
http://ru.wikipedia.org/wiki/Бинарны...нахождения_НОД
2
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
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 23:15 #5
sv011, перепишите алгоритм согласно ссылке, которую я вам кинул
1
Andrey1945
0 / 0 / 0
Регистрация: 21.09.2015
Сообщений: 40
25.10.2015, 19:02 #6
Помогите пожалуйста такой код под java сделать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2015, 19:02
Привет! Вот еще темы с ответами:

Найти наибольший общий делитель двух чисел используя алгоритм Евклида - C++
Найти наибольший общий делитель двух чисел используя алгоритм Евклида. Подскажите как написать программу...

Найти наибольший общий делитель двух введенных чисел, используя алгоритм Евклида - C++
Тема: Функции2. 6. Найти наибольший общий делитель (ндс) двух введенных чисел, используя алгоритм Евклида. Алгоритм Евклида: отнимать от...

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

Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел - C++
Напишите пожалуйста код =)


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

Или воспользуйтесь поиском по форуму:
6
Yandex
Объявления
25.10.2015, 19:02
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru