У нас уже вышло много статей про собеседования, где рассказываем, что делать, как подготовиться и чего ожидать:
Но кроме теории и головоломок на собеседовании часто встречается практика — нужно решать кодом небольшую задачку. Так вас оценивают как программиста:
- насколько простой и понятный будет ваш код;
- как вы его оформляете;
- каким методом решена задача — в лоб или красиво и элегантно.
Сегодня будет классическая задача с собеседований на знание JavaScript на уровне джуниора:
найдите все простые множители любого выбранного числа.
Эта задача имеет мало отношения к реальной работе (вчера мы даже писали почему). Она нужна скорее для знакомства с вашим стилем программирования.
Давайте разберём эту задачку.
Что такое простые множители?
Простое число — это такое число, которое делится нацело только на единицу и на само себя. Например, число 7 простое, потому что его можно разделить только на 1 и 7. А число 8 — не простое, потому что у него много делителей: 1, 2, 4 и 8.
Если значение можно получить умножением одних чисел на другие, не считая единицы и самого числа, то такие числа называют множителями числа. В нашем примере у числа 8 множители 2 и 4. У числа 18 множителей больше — 2, 3, 6 и 9:
2 × 9 = 18
3 × 6 = 18
6 × 3 = 18
9 × 2 = 18
В нашей задаче нужно найти все простые множители числа. Это значит, что среди всех множителей нужно выбрать только простые числа. Разберём множители числа 18:
2 — простое, подходит для ответа
3 — простое, тоже подходит для ответа
6 — составное, потому что 6 = 2 × 3
9 — составное, потому что 9 = 3 × 3
Значит, если мы введём число 18, программа должна выдать в ответ числа 2 и 3.
Логика решения будет такой:
Делаем одну большую функцию, внутри которой и будут происходить все вычисления. В конце работы мы скормим этой функции искомое число.
Внутри этой функции делаем вспомогательную функцию — она будет проверять, простое число ей передали на проверку или не простое.
После этого перебираем все числа от 2 до введённого числа и смотрим, делится введённое число на это или нет. Если делится, то проверяем, простое оно или нет. Если простое — добавляем в массив с решением.
Наконец вызываем нашу большую функцию, передаём ей число на проверку и смотрим результат в консоли.
Теперь читайте комментарии в итоговом коде:
// Основная функция, внутри которой происходят все вычисления. На вход она получает число, для которого нужно найти все простые множители
function PrimeNumber(InputNumber) {
// объявляем внутреннюю функцию — она проверяет, простое число ей передали или нет
function isPrime(m) {
// переменная для цикла
var i;
// перебираем все числа от 2 до переданного числа
for (i = 2; i < m; i++) {
// если число делится нацело на любое число из этого диапазона, значит, оно не простое
if (m % i === 0) {
// возвращаем признак того, что это не простое число
return false;
}
}
// если мы дошли досюда, значит, ни один делитель не подошёл, поэтому перед нами простое число
return true;
}
// переменная для цикла
var j;
// массив, где будем хранить все найденные простые множители
var sequence = [];
// точно так же проходим все числа от 2 до введённого числа
for (j = 2; j < InputNumber; j++) {
// если введённое число делится нацело и делитель — простое число,
if (InputNumber % j === 0 && isPrime(j)) {
// то добавляем это число в массив с простыми множителями
sequence.push(j);
}
}
// в конце основной функции возвращаем её значение — массив с простыми делителями
return sequence;
};
// запускаем программу и смотрим результат
console.log(PrimeNumber(123456789));Почему вы не используете квадратный корень, как все?
Почти в каждом решении из интернета есть один лайфхак: цикл перебирает множители не до самого числа, а меньше: до квадратного корня этого числа. Например, если бы мы искали простые множители числа 64, то цикл прошёл бы до числа 8.
На поверхности это выглядит круто: мы можем оптимизировать алгоритм, сделав его невозможно быстрым — ведь он будет перебирать очень небольшой объём множителей. Но конкретно в нашем алгоритме у такого хода есть нюанс.
Математическое объяснение приёма с квадратным корнем звучит так: если число можно разложить на два множителя, то оба эти множителя одновременно не могут быть больше квадратного корня этого числа. По-другому — один из множителей точно не будет больше квадратного корня. Соответственно, другой множитель может быть больше.
Проблема в том, что мы не находим множители попарно. Мы находим их один за другим. Наш алгоритм не помнит, какие множители он уже нашёл.
Например, возьмём число 77. Оно состоит из двух простых множителей: 7 и 11. Квадратный корень из 77 равен 8,77. В паре множителей 7 и 11 только один из них больше 8,77, значит, условие выполняется: оба множителя одновременно не больше квадратного корня нашего числа.
Теперь, если бы мы искали множители вручную, мы бы действительно перебирали все множители до 8,77. Мы бы нашли множитель 7, разделили бы 77 на 7 и получили бы 11. Так мы бы получили два множителя: 7 и 11. Это простые числа, нас этот результат удовлетворил бы.
Но наш алгоритм ищет множители не парами, а по одному. Если бы мы перебирали множители до 8,77, то мы бы нашли только множитель 7. Множитель 11 мы бы не нашли, ведь алгоритм остановился бы.
Поэтому конкретно с нашим алгоритм трюк с квадратным корнем не пройдёт. Но можно использовать другие оптимизации.
👉 На подумать: сейчас в алгоритме мы перебираем все числа от двойки до введённого числа, но есть способ сократить количество переборов. Попробуйте найти его самостоятельно.
