C++, Нахождение НОД

Question

C++, Нахождение НОД

Борис Селиванов Знаток (407), закрыт 1 год назад

И снова всем хелло! Решал тут задачку на нахождение НОДА, вот код:
#include <iostream>
using namespace std;
int main(){
int n, del;
cin >> n;
del = 2;
while (n % del != 0){
del += 1;
}
cout << del;
}
На одном из тестов затупила и выполняла слишком долго. Почему? И можете предложить "починенную" версию кода?

Дополнен 1 год назад

Всем спасибо за ответы, решил сам) Функцию gcd еще не изучал просто, вот код и не принял...

Answer 1

Проблема с вашим кодом на C++ заключается в том, что вы используете простой перебор для нахождения делителя. Это работает, но когда вводимое число очень большое, а делитель является простым числом, процесс занимает много времени.

Вместо простого перебора можно использовать более эффективный алгоритм нахождения наибольшего общего делителя (НОД) - алгоритм Евклида. Алгоритм Евклида основан на том факте, что НОД двух чисел не изменится, если к большему числу присоединить остаток от деления наименьшего числа на большее число.

Вот починенная версия кода, использующая алгоритм Евклида:

```cpp
#include <iostream>
using namespace std;

int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

int main() {
int n;
cin >> n;
int del = gcd(n, 2);
cout << del;
return 0;
}
```

В этой версии кода функция `gcd` принимает два аргумента и находит их наибольший общий делитель с помощью алгоритма Евклида. Затем в основной функции `main` вызывается `gcd` с аргументами `n` и `2`, и результат сохраняется в переменной `del`. Затем `del` выводится на экран. Этот код будет работать гораздо быстрее, особенно при больших значениях `n`.

Answer 2

Во первых, это НЕ НОД: НОД - это НАИБОЛЬШИЙ общий делитель ДВУХ чисел.
Ты же считаешь НАИМЕНЬШИЙ делитель ОДНОГО числа больший 1.

Если тебе нужен именно НОД, то:

 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

Если же тебе нужен более быстро работающий аналог твоего кода, то меняешь:

 del = 2;
while (n % del != 0){
del += 1;
}

На:

 for (del = 2; del * del <= n && n % del; ++del);
if (n % del) { del = n; }

Искать делители надо не до n, а до √n