Задача с собеседования: найти все простые множители

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

Но кро­ме тео­рии и голо­во­ло­мок на собе­се­до­ва­нии часто встре­ча­ет­ся прак­ти­ка — нуж­но решать кодом неболь­шую задач­ку. Так вас оце­ни­ва­ют как программиста:

  • насколь­ко про­стой и понят­ный будет ваш код;
  • как вы его оформляете;
  • каким мето­дом реше­на зада­ча — в лоб или кра­си­во и элегантно.

Сего­дня будет клас­си­че­ская зада­ча с собе­се­до­ва­ний на зна­ние 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 мы бы не нашли, ведь алго­ритм оста­но­вил­ся бы.

Поэто­му кон­крет­но с нашим алго­ритм трюк с квад­рат­ным кор­нем не прой­дёт. Но мож­но исполь­зо­вать дру­гие оптимизации. 

👉 На поду­мать: сей­час в алго­рит­ме мы пере­би­ра­ем все чис­ла от двой­ки до вве­дён­но­го чис­ла, но есть спо­соб сокра­тить коли­че­ство пере­бо­ров. Попро­буй­те най­ти его самостоятельно.

Текст:

Миха­ил Полянин

Редак­ту­ра:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев