Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   JS задача. Взаимно простые числа (https://javascript.ru/forum/misc/51867-js-zadacha-vzaimno-prostye-chisla.html)

sashok 22.11.2014 22:14

JS задача. Взаимно простые числа
 
Добрый вечер! Пытаюсь решить задачу:
Составить программу, проверяющую, будет ли взаимно просты два натуральных числа.

Не могли бы вы описать ход решения. Не программой, а объяснением того как бы вы это делали.

Вот что я думаю:
Сперва создать две переменные prompt, в которые будут вноситься числа. Потом с помощью цикла перебрать на какие числа они делятся без остатка, потом сравнить эти два массива, если есть схожие числа, то выдавать сообщение о том, что числа являются не взаимными!
Кто что думает?

ksa 22.11.2014 22:53

Цитата:

Сообщение от sashok
Сперва создать две переменные prompt

Чем провинились инпуты?

Цитата:

Сообщение от sashok
перебрать на какие числа они делятся без остатка, потом сравнить эти два массива, если есть схожие числа, то выдавать сообщение о том, что числа являются не взаимными

Незачем это делать от начала до конца... Достаточно одного делителя найденого в минимальном из чисел и они уже невзаимнопросты.
Такой алгоритм будет короче

Яростный Меч 23.11.2014 00:47

Можно найти наибольший общий делитель (по алгоритму Евклида), и если он равен 1, то взаимно простые.

bes 23.11.2014 00:51

Взаимно простые числа
Алгоритм Евклида
Реализации алгоритмов/Алгоритм Евклида

function isCoprime (a, b) {
	console.log(a + "," + b);
	var num;
	while ( b ) {
		num = a % b;
		console.log(num);
		a = b;
		b = num;
	}
	if (Math.abs(a) == 1) {
		console.log(true);
		return true;
	}
	console.log(false);
	return false;
}
isCoprime(1071, 462);
isCoprime(14, 25);
isCoprime(15, 25);
isCoprime(1, 1);

bes 23.11.2014 00:51

Цитата:

Сообщение от Яростный Меч
Можно найти наибольший общий делитель (по алгоритму Евклида), и если он равен 1, то взаимно простые.

немного опередил :)

sashok 23.11.2014 10:16

спасибо за разъяснения!


Часовой пояс GMT +3, время: 17:43.