Если вы потратили какое-то время на войны кодов, определение того, является ли число простым, является общей темой среди категорий проблем. Когда я впервые начал кодировать, я подумал, что перебрать все числа от 1 до num и проверить, делится ли оно, было отличным подходом. Однако, как только я узнал о большой нотации O, я был огорчен!

После некоторого исследования и чтения wiki в эти выходные я нашел отличную функцию для определения того, является ли число простым с сублинейным временем O (n). Я нашел следующее решение:

function isPrime (num) {
  if (num <= 1) {
    return true
  } else if (num <= 3) {
    return true
  } else if (num%2 === 0 || num%3 === 0) {
    return false
  }
 
  let i = 5
  while (i*i <= num) {
    if (num%i === 0 || num%(i+2) === 0) {
      return false
    }
    i += 6
  }
  return true
}

Подход

  1. Проверяет, является ли число 0, 1 или отрицательным. Возвращает true, если число находится в этом диапазоне.
  2. Проверяет, равно ли число 2 или 3. Возвращает true, если число равно 2 или 3.
  3. Последний оператор if возвращает, что число не является простым, если оно делится на 2 или 3.
  4. Последняя часть этой функции самая сложная - цикл while! По сути, он проверяет каждое нечетное число, которое не делится на 3, пока оно не станет больше квадратного корня из числа. Например, первые i и i + 2 будут 5 и 7. Следующие i и i + 2 будут 11 и 13. Он не проверяет 9 или 15, потому что оба делятся на 3 и попали бы в последний else if заявление.
  5. Наконец, возвращает true, если число не делилось ни на какие i или i+2 записи, потому что число простое.

O(n)

Если мы предположим, что n - это число, переданное в isPrime, O (n) моего первоначального [не так хорошо] подхода будет O (n). Следовательно, эта временная сложность будет линейной. Это нормально, если все, что вы делаете, - это проверка, но во многих случаях эта функция является вспомогательной, и проверка того, является ли список чисел простым, будет экспоненциальной.

Вышеупомянутая функция isPrime будет O (n ^ ¹ / 2). Это означает, что временная сложность будет сублинейной, что значительно снизит временную сложность более крупной функции.

В заключение

Есть много способов проверить, является ли число простым. Существуют эвристические программы, которые проверяют вероятность того, что число является простым. Другая стратегия - использование теоретико-числового метода. Если вы нашли какие-либо интересные способы решения этой проблемы, прокомментируйте их ниже или напишите мне по адресу [email protected].