Мне так понравился вызов, что мне пришлось написать об этом небольшой пост. Это с сайта Project Euler:
Наибольший простой фактор
Простые множители 13195: 5, 7, 13 и 29.
Какой самый большой простой делитель числа 600851475143?
Ой ... это огромное количество! Но мы справимся, не волнуйтесь! Давайте быстро посмотрим, что такое простое число:
простое число (или простое число) - это натуральное число больше 1, не имеющее положительных делителей, кроме 1 и самого себя. например 3, 5, 7, 9 и т. Д.
Также:
Факторы - это числа, которые мы можем умножить вместе, чтобы получить другое число: Пример: 2 и 3 - это факторы 6, потому что 2 * 3 = 6.
Большой! Спасибо, Википедия! Обладая этими знаниями, мы готовы перейти к следующему шагу, который заключается в сравнении нескольких чисел и их простых множителей. Это поможет нам лучше понять, как решить нашу проблему с помощью наилучшего решения!
Пример 1 ~ 12:
Первым делом разделите число (12 в этом примере) на наименьшее простое число, которым является 2:
12 / 2 = 6
Как мы видим, 6 делится поровну на 2, поэтому мы делаем шаг снова:
6 / 2 = 3
Ибо… Roadblock. Каждый раз, когда мы сталкиваемся с Roadblock, мы увеличиваем divisor на 1:
2 + 1 = 3
Затем продолжаем:
Число / делитель:
3 / 3 = 1
Идеально! Мы добрались до 1, что является нашей целью. Это означает, что основными множителями 12 являются: 2 * 2 * 3, из которых 3 - наш наибольший простой множитель!
Пример 2 ~ 20:
Повторяя те же шаги, что и в нашем первом примере:
20 / 2 = 10
10 / 2 = 5
5 больше не делится на 2 без остатка, поэтому мы добавляем к нему 1 и получаем 3. Но опять 5 он не делится без остатка на 3… ни на 4… но это с 5:
5 / 5 = 1
Большой! 1 снова. Основные множители 20: 2 * 2 * 5, из которых 5 - наш самый большой простой множитель!
Здесь мы начинаем видеть закономерность. Но давайте продолжим еще один пример:
Пример 3 ~ 180
180 / 2 = 90
90 / 2 = 45
Roadblock… Добавление до 3:
45 / 3 = 15
15 / 3 = 5
Roadblock снова… Добавление до 4 - ›Roadblock… Добавление до 5:
5 / 5 = 1
Попался! : D Основные множители 180: 2 * 2 * 3 * 3 * 5, из которых 5 снова наш наибольший простой множитель!
Это алгоритм, который мы собираемся реализовать в JavaScript: пока наш number равномерно делится на наш divisor, мы делим number на divisor, когда он больше не делится без остатка, мы увеличиваем divisor на 1. Легко, правда? Напишем для него код:
Решение JavaScript
Как мы уже говорили выше, нам понадобится divisor, у которого будет начальное значение: 2:
var divisor = 2;
Также давайте сохраним этот большой number в переменную:
var divisor = 2; var number = 600851475143;
Хороший. Теперь о цикле while. Пока number больше 1…
var divisor = 2;
var number = 600851475143;
while(number > 1){
}
Если number делится на divisor:
var divisor = 2;
var number = 600851475143;
while(number > 1){
if(number % divisor === 0){
}
}
Разделите number на divisor:
var divisor = 2;
var number = 600851475143;
while(number > 1){
if(number % divisor === 0){
number /= divisor;
}
}
Примечание. x /= divisor - это то же самое, что сказать: x = x / divisor.
Иначе увеличьте divisor:
var divisor = 2;
var number = 600851475143;
while(number > 1){
if(number % divisor === 0){
number /= divisor;
} else {
divisor++;
}
}
Поздравляем! По окончании цикла while делитель будет равен наибольшему простому множителю 600851475143.
var divisor = 2;
var number = 600851475143;
while(number > 1){
if(number % divisor === 0){
number /= divisor;
} else {
divisor++;
}
}
console.log(divisor); // the largest prime factor of 600851475143
Я не дам тебе ответа. : D Вы можете запустить код и написать в комментариях под правильным ответом. ;)
Заключение
Это испытание определенно доставило мне большое удовольствие. Я многому научился, просто пытаясь решить эту проблему другим способом, чем я первоначально думал. : D Я бы сказал, что стоит потратить время на поиск лучшего решения проблемы.
Небольшое примечание: мы видим, что 2 - единственное четное простое число. Это означает, что когда делитель становится 3, мы можем увеличить его на 2 вместо 1, например: 2, 3, 5, 7, 9…
Также есть дополнительное условие, которое мы могли бы иметь в цикле while, чтобы алгоритм был намного более эффективным для даже большие числа. Но я позволю тебе узнать, что это. ^ _ ^
Надеюсь, вам понравился этот вызов. Если да, то я был бы искренне признателен, если вы нажмете кнопку Рекомендовать. 💚
