не достаточно; НОД(7,14) например равен 7BBB писал(а): 1) при поиске НаибОД достаточно проверять числа не от 2 до min (a,b), а от 2 до min (a,b) /2.
Код: Выделить всё
int getNODab(int a, int b) // вычисляем НОД-наибольший общий делитель чмсел а и b
{ for (int i=min(a,b); i>0; i--) if (a%i==0 && b%i==0) return i; }
Код: Выделить всё
long getNODab(long a, long b)
{
long NOD = 1;
long p,c;
long maxp; //максимальное непроверенное число на предмет делятся ли на него a и b
c = min(a,b);
maxp = p = FindNearestSimpleNumberNotGreaterThan(c);}
do
{
if (a%p==0 && b%p==0)
{NOD*=p; a=a/p; b=b/p;c = min(a,b);
p = FindNearestSimpleNumberNotGreaterThan(c); p = min(p,maxp);}
else {p = GetPrev(p); maxp=p;}
}while(p>1);
return NOD;
}
Ну да, переклинило малость, забыл, что тут, в отличие от проверки на простое число, можно на самое себя делить.licenok писал(а):не достаточно; НОД(7,14) например равен 7
Код: Выделить всё
int CalcNOD(int Num1, int Num2)
{
int max=0;
int min=0;
int num0=0;
if (Num1 > Num2)
{
max=Num1;
min=Num2;
}
else if (Num1 < Num2)
{
max=Num2;
min=Num1;
}
else
{
num0=Num1;
return num0;
}
while (1)
{
num0 = max - min;
if (min > num0)
{
max=min;
min=num0;
}
else if (min == num0)
{
return num0;
}
else if (min < num0)
{
max=num0;
}
}
return 1;
}