Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 07.09.2017, 13:14
Аватар для DynkanMaclaud
Профессор
Отправить личное сообщение для DynkanMaclaud Посмотреть профиль Найти все сообщения от DynkanMaclaud
 
Регистрация: 08.08.2014
Сообщений: 261

числа больше 2 ^53
имеется следующее задание
Наименьшее число m, такое, что m! делится без остатка на 10 — это m=5 (5! = 120). Аналогично, наименьшее число m, такое, что m! делится без остатка на 25 — это m=10. В общем случае, значение функции s(n) равно наименьшему числу m, такому что m! без остатка делится на n. Определим функцию S(M, N) = ∑s(n) для всех n ∈ [M, N]. К примеру, S(6, 10) = 3 + 7 + 4 + 6 + 5 = 25. Найдите S(3200000, 3300000).

написал следующий код:
https://jsfiddle.net/m8n1LLqz/

в примере взял от 6 до 10, но если вы возьмете 3200000, 3300000, то при нахождении числа, факториал которого будет без остатка делится на 3200000, получаем Infinity, что делать не знаю... выручайте
Ответить с цитированием
  #2 (permalink)  
Старый 07.09.2017, 18:17
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,005

Конечно же, тут не надо вычислять факториал и проверять его делимость

надо разложить делитель на простые множители. посмотреть степени этих множителей. от этого строить искомое число.

например, если у нас число 18. Это 2 * 3^2. здесь ответ будет 6 (6! делится на 18). а почему? да потому, что в произведении 1*2*3*4*5*6 встретится и двойка, и обе тройки (в числах 3 и 6). В общем, как-то так.

другое дело, насколько это будет быстро. Оную операцию надо проделать 100000 раз. Раскладывание на простые множители - не такая простая вещь. Потому тут надо что-то ещё думать.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Простые числа, не превосходящие заданного числа. jutochka123 Общие вопросы Javascript 2 30.09.2017 13:05
Показ следующего числа в зависимости от нажатой кнопки TTATPuOT jQuery 1 09.10.2015 18:56
JS задача. Взаимно простые числа sashok Общие вопросы Javascript 5 23.11.2014 10:16
Есть числа от (0 до 100) что бы все эти числа были заменины в итоге например 110 impi Общие вопросы Javascript 4 08.10.2014 08:30
Необычный алгоритм. Неповторяющиеся числа. broadcast77 Общие вопросы Javascript 5 13.01.2014 10:46