Нужно написать функцию, которая принимает на вход 1 число, и возвращает следующее простое число после переданного

Question

Не могу написать функцию, которая принимает на вход 1 число, и возвращает следующее простое число после переданного. То есть если в функцию передать число 6, то функция вернет число 7. Если передать 120, то вернет 127, и так далее.
Можно сделать при помощи перебора, но я не понимаю как его применить к простым числам
const startFrom = 100;

for (let i = startFrom; ; i++) {
    if (i % 87 === 0) {
    console.log(i);
    break;
    }
}

Darth · Answer

быть может не самый быстрый и крутой способ, но работает

// Начало перебора. 
let i = 2; 
// Массив делителей (простых чисел)
const dividers = [i]; 

function st(n){
  // сначала ищем число больше данного в массиве уже найденных делителей, чтоб лишний раз не считать.
  const next = dividers.find(d => d > n);
  // если такое есть - просто выводим его
  if(next) return next;
  // перебираем числа по одному, пока самый большой найденный делитель меньше либо равен полученному числу
  while(dividers[dividers.length - 1] <= n) { 
    // проверяем, делиться ли число на какое-либо из уже найденных простых
    if(dividers.every(d => i%d)){ 
      // если нет - добавляем в массив простых чисел
      dividers.push(i); 
    }
    // увеличиваем счетчик. в следующий раз подсчет начнется с того места, на котором остановился (мемоизация)
    i++; 
  }
  // цикл кончился - последний найденный делитель в массиве - искомое простое число больше данного.
  return dividers[dividers.length - 1]; 
}

calc.onclick = () => res.value = st(inp.value);

<input id='inp'/>
<button id='calc'>Calc</button>
<input id='res'/>

Нужно написать функцию, которая принимает на вход 1 число, и возвращает следующее простое число после переданного

One Answer

Add your own answers!

Ask a Question