Поможете решить задачку на javascript?

Question

[Umid]

Решаю задачи по js и код почему то не находит подходящее число!

Вопрос:

2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.

Какое самое маленькое число делится нацело на все числа от 1 до 20?

Мой js код:

var arrayForF = [];

		for(var i = 1; i < 10000000 ;i++){
			var f1 = i / 1;
			var f2 = i / 2;
			var f3 = i / 3;
			var f4 = i / 4;
			var f5 = i / 5;
			var f6 = i / 6;
			var f7 = i / 7;
			var f8 = i / 8;
			var f9 = i / 9;
			var f10 = i / 10;
			var f11 = i / 11;
			var f12 = i / 12;
			var f13 = i / 13;
			var f14 = i / 14;
			var f15 = i / 15;
			var f16 = i / 16;
			var f17 = i / 17;
			var f18 = i / 18;
			var f19 = i / 19;
			var f20 = i / 20;
			
			if(f1%1 && f2%1 && f3%1 && f4%1 && f5%1 && f6%1 && f7%1 && f8%1 && f9%1 && f10%1 && f11%1 && f12%1 && f13%1 && f14%1 && f15%1 && f16%1 && f17%1 && f18%1 && f19%1 && f20%1 ){
				arrayForF.push(i);
			}
		}
				document.write(arrayForF);

В чём же моя ошибка?? Или число больше 10 000 000??

Answer 1

[Lynn «Кофеман»]

У вас задача найти наименьшее общее кратное 20 чисел. Ну так и нужно его искать, а не заниматься бессмысленным перебором.

Вот, например, самое простое решение в лоб: jsfiddle.net/moq36zrg/3
Хотя в википедии есть и другие алгоритмы https://en.wikipedia.org/wiki/Least_common_multipl...

Answer 2

[Вячеслав Овчинников]

Это число 232792560.
jsfiddle.net/moq36zrg/1

Comments

[Stalker_RED]

Ускорил в 20 раз jsfiddle.net/moq36zrg/2

[Вячеслав Овчинников]

Ну да )) Просто я не заморачивался - набросал по быстрому!

[Lynn «Кофеман»]

Ускорил ещё :)
jsfiddle.net/moq36zrg/3

Answer 3

[Дмитрий Ковальский]

Чисто алгоритмически у вас тут сотни и тысячи лишних операций. Если уж начали реализовывать ТАК, то делите только на 11,13,14,16,17,18,19 и 20.

Comments

[ChernovGV]

Да, но если нет алгоритма который будет формировать данный массив, то такой подход использовать нельзя. ИМХО. Вы можете предложить какой-то вариант?

[Дмитрий Ковальский]

ChernovGV: Конечно. взять массив чисел на которые надо проверять и с меньшего делать следующую проверку -

if(numbers[i+n]%numbers[i])
   delete numbers[i]

Идея примерно такова. надо только подогнать под конкретный язык.

[Дмитрий Ковальский]

ChernovGV: Нашел баг, потом нашел решение...а потом Алексей Тен дал ссылку на нормальные мат.алгоритмы.

Answer 4

[Антон Федорян]

Алексей Тен Наверное все-таки НОК (наименьшее общее кратное) надо находить, а не НОД.

Comments

[Lynn «Кофеман»]

Ага. Всегда в этих названиях путался :)