БЛОГ НА HUSL


Не могу понять алгоритм определения число простое или нет

Автор вопроса: Nikon 

simpleNum:
for (let i = 2; i < 50; i++) {
    for (let j = 2; j < i; j++) {
        if (i % j == 0) continue simpleNum;
    }

    console.log(i);
}

Задача была вывести простые число от 1 до 50 и за 2 часа у меня так и не получилось решить задачу. Я полез в интернет и нашел такое решение, но я немного не понимаю алгоритм действий в этом решении. Разъясните пожалуйста


Источник

Ответы (2 шт):

Автор решения: xaker1337

Цикл for i выполняет цикл j, потом цикл i++ выполняет цикл j и т.д.

→ Ссылка
Автор решения: EzioMercer

Перед тем как начать рассматривать алгоритм, рассмотрим саму проблему

Что такое простое число?

Простое число — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p

Источник: Википедия

По началу понять число простое или нет достаточно просто, например 2, 3, 5, 7 и т.д.

А вот 137 простое число или нет? Уже не так очевидно... А если взять число 1298754829483? Значит нам явно нужен алгоритм для определения число простое или нет

Самый простой способ - это перебрать абсолютно все числа от 2 до заданного числа (не включительно) и проверять делится ли нацело заданное число на проверочное число? Если делится, значит число не простое, т.к. нашёлся делитель помимо 1 и самого числа

Почему от 2? - Потому что на 1 нацело делится любое натуральное число, и потому в лишний раз проверять на его делимость не имеет смысла

Почему до заданного числа (не включительно)? - На само число проверять нет смысла, т.к. любое натуральное число нацело делится на самого себя, а на большие числа тем более нет смысла, т.к. если натуральное число поделить на большие натуральные числа, то мы будем получать числа между 0 и 1

Напишем такой функционал:

const isPrime = num => {
  if (num === 1) return false;
  
  for (let i = 2; i < num; ++i) {
    if ((num % i) === 0) return false;
  }
  
  return true;
}

console.log(1, 'is prime: ', isPrime(1));
console.log(2, 'is prime: ', isPrime(2));
console.log(3, 'is prime: ', isPrime(3));
console.log(4, 'is prime: ', isPrime(4));
console.log(5, 'is prime: ', isPrime(5));
console.log(6, 'is prime: ', isPrime(6));
console.log(7, 'is prime: ', isPrime(7));
console.log(8, 'is prime: ', isPrime(8));
console.log(9, 'is prime: ', isPrime(9));
console.log(137, 'is prime: ', isPrime(137));
console.log(1298754829483, 'is prime: ', isPrime(1298754829483));

P.S. Проверка на единицу нужна, потому что 1 единственное натуральное число, которое не является ни составным ни простым

У вас есть диапазон чисел от 1 до 50, а значит мы можем просто пройтись по нему циклом и для каждого числа вызывать isPrime

const isPrime = num => {
  if (num === 1) return false;
  
  for (let i = 2; i < num; ++i) {
    if ((num % i) === 0) return false;
  }
  
  return true;
}

for(let i = 1; i < 50; ++i) {
  if (isPrime(i)) console.log(i);
}

В целом это всё что вам нужно. Но теперь вернёмся к синтаксису, который вы нашли.

Перепишем то что у нас уже есть на похожий синтаксис:

checkNum: for(let i = 1; i < 50; ++i) {
  if (i === 1) continue;
  
  for (let j = 2; j < i; ++j) {
    if ((i % j) === 0) continue checkNum;
  }
  
  console.log(i);
}

По сути я просто перенёс функцию внутрь цикла. Но теперь у нас появились continue. Они играют роль return, который был у нас в функции. Как return может досрочно остановить выполнение функции, так и continue приостанавливает текущую итерацию цикла, в котором находится, но если мы хотим чтобы continue останавливал текущию итерацию родительского цикла, то нам нужны метки

Т.к. мы заранее знаем, что 1 - это не простое число, то можем его убрать как из верхнего цикла (и начать с 2) так и саму провекру на единицу:

checkNum: for(let i = 2; i < 50; ++i) {
  for (let j = 2; j < i; ++j) {
    if ((i % j) === 0) continue checkNum;
  }
  
  console.log(i);
}

Что ровно то же самое что и у вас, с мелкими изменениями:

simpleNum:
for (let i = 2; i < 50; i++) {
    for (let j = 2; j < i; j++) {
        if (i % j == 0) continue simpleNum;
    }

    console.log(i);
}

Надеюсь теперь стало понятнее :)

Доп. материал (оптимизация)

Наш алгоритм, котрый мы рассматривали выше, можно очень сильно оптимизировать

Давайте представим входное число k как произведение двух чисел, тогда k = n * m. Думаю это очевидно что чем больше n тем меньше m и наоброт. Отсюда вытекает, что должен быть момент, когда n и m уровнятся. А когда же это произойдёт?

k = n * m; n = m;

k = n * n

k = n ^ 2

n = ±sqrt(k)

s = sqrt(k);

n = ±s

n ∈ N

n = s

И так мы выяснили что n и m встретятся когда оба будут равны квадратному корню от входного числа k (s). Отсюда следует, что проверять деление на числа после s не имеет смысла, следовательно ограничиваем наши проверки этим числом и тогда количество операций для определения явялется ли число простым сильно сокращается. Сделаем эксперимент:

const isPrimeWithOpt = num => {
  let steps = 1;
  if (num === 1) return {steps, result: false};
  
  for (let i = 2; i <= Math.sqrt(num); ++i) {
    ++steps;
    
    if ((num % i) === 0) return {steps, result: false};
  }
  
  return {steps, result: true};
}

const isPrimeWithoutOpt = num => {
  let steps = 1;
  if (num === 1) return {steps, result: false};
  
  for (let i = 2; i < num; ++i) {
    ++steps;
    
    if ((num % i) === 0) return {steps, result: false};
  }
  
  return {steps, result: true};
}

const testDatas = [
  1,
  2,
  3,
  4,
  5,
  6,
  7,
  8,
  9,
  137,
  7919,
  2147483647,
  1298754829483
];

for (const testData of testDatas) {
  const {result: result1, steps: steps1} = isPrimeWithOpt(testData);
  const {result: result2, steps: steps2} = isPrimeWithoutOpt(testData);
  
  console.log(testData, 'is prime with/without optimization:', result1, '/', result2);
  console.log('Steps with/without optimization:', steps1, '/', steps2);
  console.log('==============================');
}

Где мы видим, что если число не простое, то количество операций бывает одинаковым, но если число простое, то мы пропускаем огромное количество лишних итераций

Двигаемся дальше (Спасибо avp)

Если в оптимизации не останавливаться на sqrt, то легко заметить, если число не делится на 2, то на остальные четные делить не надо. Таким образом надо идти в цикле от 3 до sqrt через 2 (т.е. проверять только нечетные)

Действительно! Зачем проверять делимость числа на 4, 6, 8, ... 2n если ещё в самом начале мы можем выяснить делится ли число на 2 или нет?

Почему мы имеем право так делать? - Потому что, единственным чётным простым числом является 2, а значит можно смело говорить, что число не простое, если оно делится на 2 и не равен 2-ум. Либо дргуими словами - все простые числа кроме 2 - нечётные, а значит если у числа нет делителя 2, то искать делители вида 2n не имеет смысла, потому что если бы они были, то сама 2-ка обязательно должна была бы быть в списке делителей числа, т.к. сами числа вида 2n делятся на 2

Как же нам пропускать все чётные делители? Элементарно, вместо ++i писать i += 2 и начинать цикл не с 2, а с 3, получится 3, 5, 7, 9, 11, ... 2n + 1

С учётом вышесказанного можем программу переписать и снова провести эксперимент

setTimeout(() => {
  const isPrime = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    for (let i = 2; i < num; ++i) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
    }

    return {steps, result: true};
  }

  const isPrimeOpt = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    for (let i = 2; i <= Math.sqrt(num); ++i) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
    }

    return {steps, result: true};
  }

  const isPrimeOpt2 = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    ++steps;
    if ((num % 2) === 0) return {steps, result: num === 2};
    /*
      if ((num % 2) === 0) {
        if (num === 2) return {steps, result: true};
        else return {steps, result: false};
      }
    */

    for (let i = 3; i <= Math.sqrt(num); i += 2) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
    }

    return {steps, result: true};
  }

  const testDatas = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    137,
    7919,
    2147483647,
    1298754829483
  ];

  for (const testData of testDatas) {
    const {result: result1, steps: steps1} = isPrime(testData);
    const {result: result2, steps: steps2} = isPrimeOpt(testData);
    const {result: result3, steps: steps3} = isPrimeOpt2(testData);

    console.log(testData, 'is prime (method 1 / 2 / 3):', result1, '/', result2, '/', result3);
    console.log('Steps (method 1 / 2 / 3):', steps1, '/', steps2, '/', steps3);
    console.log('==============================');
  }
  
  document.querySelector('.loading').style.display = 'none';
}, 16)
* {
  margin: 0;
  padding: 0;
  box-sizing: border-box;
}

body {
  height: 100vh;
}

.loading {
  display: flex;
  flex-direction: column;
  align-items: center;
  justify-content: center;
  
  width: 100%;
  height: 100%;
  background-color: rgba(0, 0, 0, 0.5);
}

.spinner {
  width: 50px;
  height: 50px;
  
  border: 8px solid white;
  border-bottom-color: transparent;
  border-radius: 50%;
  
  animation: spin 0.5s infinite linear;
}

@keyframes spin {
  from {transform: rotate(0deg)}
  to {transform: rotate(360deg)}
}


.text {
  color: white;
}
<div class="loading">
  <div class="spinner"></div>
  <span class="text">Calculating... Please wait!</span>
</div>

Этот подход ускоряет подбор делителей практически в 2 раза по сравнению с перебором всех чисел с шагом в 1

Двигаемся дальше (Спасибо Nowhere Man)

аналогично можно отбросить числа кратные трём и проверять только числа, отвечающие формуле 6n ± 1, как указано в ответе на аналогичный вопрос на Питоне

Действительно, если взять например первую сотку чисел начиная с 1 и убрать все числа кратные 2-ум и 3-ём, то легко заметить, что начиная с 5 все числа выражаются формулой 6n ± 1, где n ∈ N

Давайте докажем это утверждение:

-- ДОКАЗАТЕЛЬСТВО ОТ ОБРАТНОГО --

Пусть `k` - некое число из полуинтервала `[5, ∞)`, которое не удовлетворяет формуле `6n ± 1`, где `n ∈ N`

Это число не может быть чётным, т.к. по условию мы убрали все числа, кратные `2`-ум =>
это число нечётное =>
оно выражается формулой `2m + 1`, где `m > 1 и m ∈ N`

Но, не забываем, что мы так же исключили все числа кратные `3`-ём =>
`2m + 1 ≠ 3j`, где `j - нечётное, j > 1 и j ∈ N` =>
`j = 2i + 1`, где `i ∈ N` =>
`2m + 1 ≠ 3(2i + 1)` =>
`2m + 1 ≠ 6i + 3` =>
`2m ≠ 6i + 2` =>
`m ≠ 3i + 1` =>
Я могу взять абсолютно любой `m`, который не удовлетворяет формуле `3i + 1` =>
Я имею право взять формулу `3i` для `m` =>
`2m + 1 = 2(3i) + 1 = 6i + 1`, а теперь заменив `i` на `n` получаем `6n + 1`

Проделав всё то же самое только для `2m - 1`, где `m > 2 и m ∈ N`, мы получим `6n - 1`

И так мы пришли к противоречию с изначальным утверждением, т.к. получили что любое натуральное
число после исключения чисел кратных `2`-ум и `3`-ём в полуинтервале `[5, ∞)` можно выразить
либо как `6n + 1` либо как `6n - 1`

С учётом вышесказанного можем программу переписать и снова провести эксперимент

setTimeout(() => {
  const isPrime = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    for (let i = 2; i < num; ++i) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
    }

    return {steps, result: true};
  }

  const isPrimeOpt = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    for (let i = 2; i <= Math.sqrt(num); ++i) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
    }

    return {steps, result: true};
  }

  const isPrimeOpt2 = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    ++steps;
    if ((num % 2) === 0) return {steps, result: num === 2};
    /*
      if ((num % 2) === 0) {
        if (num === 2) return {steps, result: true};
        else return {steps, result: false};
      }
    */

    for (let i = 3; i <= Math.sqrt(num); i += 2) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
    }

    return {steps, result: true};
  }
  
  const isPrimeOpt3 = num => {
    let steps = 1;
    if (num === 1) return {steps, result: false};

    ++steps;
    if ((num % 2) === 0) return {steps, result: num === 2};
    /*
      if ((num % 2) === 0) {
        if (num === 2) return {steps, result: true};
        else return {steps, result: false};
      }
    */
    
    ++steps;
    if ((num % 3) === 0) return {steps, result: num === 3};

    let isLittleStep = false;

    for (let i = 5; i <= Math.sqrt(num); i += isLittleStep ? 2 : 4) {
      ++steps;

      if ((num % i) === 0) return {steps, result: false};
      
      isLittleStep = !isLittleStep;
    }

    return {steps, result: true};
  }

  const testDatas = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    137,
    7919,
    2147483647,
    1298754829483
  ];

  for (const testData of testDatas) {
    const {result: result1, steps: steps1} = isPrime(testData);
    const {result: result2, steps: steps2} = isPrimeOpt(testData);
    const {result: result3, steps: steps3} = isPrimeOpt2(testData);
    const {result: result4, steps: steps4} = isPrimeOpt3(testData);

    console.log(testData, 'is prime (method 1 / 2 / 3 / 4):', result1, '/', result2, '/', result3, '/', result4);
    console.log('Steps (method 1 / 2 / 3 / 4):', steps1, '/', steps2, '/', steps3, '/', steps4);
    console.log('==============================');
  }
  
  document.querySelector('.loading').style.display = 'none';
}, 16)
* {
  margin: 0;
  padding: 0;
  box-sizing: border-box;
}

body {
  height: 100vh;
}

.loading {
  display: flex;
  flex-direction: column;
  align-items: center;
  justify-content: center;
  
  width: 100%;
  height: 100%;
  background-color: rgba(0, 0, 0, 0.5);
}

.spinner {
  width: 50px;
  height: 50px;
  
  border: 8px solid white;
  border-bottom-color: transparent;
  border-radius: 50%;
  
  animation: spin 0.5s infinite linear;
}

@keyframes spin {
  from {transform: rotate(0deg)}
  to {transform: rotate(360deg)}
}


.text {
  color: white;
}
<div class="loading">
  <div class="spinner"></div>
  <span class="text">Calculating... Please wait!</span>
</div>

Этот подход ускоряет подбор делителей практически ещё на 33% по сравнению с перебором только нечётных чисел

Также статья на хабре про разные быстрые методы поиска простых чисел (C#): Ищем простые числа до триллиона за тридцать минут (2020)

→ Ссылка

licensed under cc by-sa 3.0 with attribution.