Шпаргалка «Является ли простое число» javascript-решением

Задание «Is prime» относится к простой категории и является хорошим началом для понимания более сложных алгоритмов, использующих целые числа и логические значения в качестве типов данных. Я сосредоточусь на объяснении решения, которое работает и не требует временных и пространственных затрат.

Вызов:

Напишите функцию isPrimeNumber, которая принимает число в качестве аргумента и возвращает логическое значение.

Примечание.

// номер номер

// цикл с использованием квадратного корня

// возвращаем логическое значение true/false

Пример:

Input:  num = 7
Output: true

Пояснение:

  1. Сначала мы проверяем, меньше ли число 2, и в этом случае оно не простое.
if (num < 2) {
return false;

2. Переберите все целые числа от 2 до половины числа.

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

3. Проверить, делится ли число на какое-либо целое число в цикле (т. е. остаток равен 0).

if (num % i === 0)

4. Если число делится на любое целое число в цикле, то оно не простое, и мы можем прекратить проверку.

return false;

5. если мы пройдем цикл, не найдя ни одного делителя, то число будет простым.

return true;

Решение:

function isPrimeNumber(num) {
  if (num < 2) {
    return false; 
  }
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      return false; 
    }
  }
  return true; 
}

Временная сложность:

  • Временная сложность цикла, проверяющего, делится ли число на какое-либо целое число до половины числа, составляет O(n/2) или просто O(n), где n — проверяемое число.
  • Таким образом, общая временная сложность алгоритма равна O(n), что означает, что время, необходимое для запуска алгоритма, увеличивается линейно с размером входного числа.

Сложность пространства:

  • Объемная сложность алгоритма постоянна, O(1), потому что мы используем только фиксированный объем памяти для хранения входного числа и нескольких переменных, используемых в цикле.
  • Независимо от размера входного числа алгоритм всегда использует один и тот же объем памяти.

Заключение

В целом алгоритм имеет временную сложность O(n) и пространственную сложность O(1). Это делает его эффективным решением для проверки того, является ли число простым, особенно для меньших размеров ввода. Однако для больших размеров входных данных могут потребоваться более продвинутые алгоритмы для достижения лучшей производительности.