int NOD(int A,int B)
{
for(;A!=B;A-=B)if(A<B)
{
B^=A;
A^=B;
B^=A;
}
return A;
}
простые числа..
Как Проверить, являются ли два данных числа взаимно простыми?
Цитата:
Originally posted by koder
Как Проверить, являются ли два данных числа взаимно простыми?
Как Проверить, являются ли два данных числа взаимно простыми?
Найти при помощи алгоритма Евклида их НОД. Если равен 1, то числа - взаимно простые.
Цитата:
Originally posted by Dart Bobr
Найти при помощи алгоритма Евклида их НОД. Если равен 1, то числа - взаимно простые.
Найти при помощи алгоритма Евклида их НОД. Если равен 1, то числа - взаимно простые.
Можно еще проверять делится ли без остачи данное число для всех чисел от 2 до SQRT(N), где N - проверяемое число.
Цитата:
Originally posted by Matush
Можно еще проверять делится ли без остачи данное число для всех чисел от 2 до SQRT(N), где N - проверяемое число.
Можно еще проверять делится ли без остачи данное число для всех чисел от 2 до SQRT(N), где N - проверяемое число.
Для двух достаточно больших чисел твой алгоритм будет жрать много времени.
Цитата:
Originally posted by Dart Bobr
Для двух достаточно больших чисел твой алгоритм будет жрать много времени.
Для двух достаточно больших чисел твой алгоритм будет жрать много времени.
Я привел его просто как один из алгоритмов. Он просто удивительно прост в реализации :)
Цитата:
Originally posted by Matush
Я привел его просто как один из алгоритмов. Он просто удивительно прост в реализации :)
Я привел его просто как один из алгоритмов. Он просто удивительно прост в реализации :)
Только не удивляйся, но алгоритм Евклида еще проще:D
Цитата:
Originally posted by wanja
Только не удивляйся, но алгоритм Евклида еще проще:D
Только не удивляйся, но алгоритм Евклида еще проще:D
Ок. Вот реализация моеого алгоритма:
bool IsSimple(int N)
{
int d=1;
while(d++<sqrt(N))
{
if(N%d == 0)
return false;
}
return true;
}
Хочешь сказать что алгоритм Евклида еще проще?
Да кстати я может немного не по теме пишу, потому как алгоритм мой для определения простое ли число, а не определение двух взаимопростых
Цитата:
Originally posted by Matush
Хочешь сказать что алгоритм Евклида еще проще?
Да кстати я может немного не по теме пишу, потому как алгоритм мой для определения простое ли число, а не определение двух взаимопростых
Хочешь сказать что алгоритм Евклида еще проще?
Да кстати я может немного не по теме пишу, потому как алгоритм мой для определения простое ли число, а не определение двух взаимопростых
Я возьму на себя смелость ответить тебе. Вот реализация алгоритма Евклида. (Правда он делает не совсем то, что твой=) )
Код:
Вот мой вариант
function nod(a,b: integer) : integer
begin
while a<>b do
begin
if a>b then a=a-b;
else
b=b-a;
end;
nod=a;
end;
function nod(a,b: integer) : integer
begin
while a<>b do
begin
if a>b then a=a-b;
else
b=b-a;
end;
nod=a;
end;
[QUOTE]Originally posted by lord Kelvin
Я возьму на себя смелость ответить тебе. Вот реализация алгоритма Евклида. (Правда он делает не совсем то, что твой=) )
Да, признаю, был в чем то неправ (хотя алгоритмы делают не одинаковые весчи :))))
Я возьму на себя смелость ответить тебе. Вот реализация алгоритма Евклида. (Правда он делает не совсем то, что твой=) )
Да, признаю, был в чем то неправ (хотя алгоритмы делают не одинаковые весчи :))))
Цитата:
Originally posted by Matush
[QUOTE]Originally posted by lord Kelvin
Я возьму на себя смелость ответить тебе. Вот реализация алгоритма Евклида. (Правда он делает не совсем то, что твой=) )
Да, признаю, был в чем то неправ (хотя алгоритмы делают не одинаковые весчи :))))
[QUOTE]Originally posted by lord Kelvin
Я возьму на себя смелость ответить тебе. Вот реализация алгоритма Евклида. (Правда он делает не совсем то, что твой=) )
Да, признаю, был в чем то неправ (хотя алгоритмы делают не одинаковые весчи :))))
Ты ни чем не ошибся, и был прав. Так как во-первых твой код работающий, а во-вторых мы не спорили.=)