Prime number

proof prime number

O(n)

JS

// Big O is O(sqrt(n))
const isPrime = (num) => {
  if (num < 2) {
    return false;
  }
  
  let root = Math.sqrt(num);
  
  for (let i = 2; i <= root; i += 1) {
    if (num % i === 0) {
      return false;
    }
  }
  
  return true;
};

O(sqrt(n))

JS

// Big O is O(sqrt(n))
const isPrime = (num) => {
  if (num < 2) {
    return false;
  }
  
  let root = Math.sqrt(num);
  
  for (let i = 2; i <= root; i += 1) {
    if (num % i === 0) {
      return false;
    }
  }
  
  return true;
};

python

import math


def is_prime(num):
    if num < 2:
        return False

    root = math.sqrt(num)
    i = 2
    while i <= root:
        if num % i == 0:
            return False
        i += 1
    return True

What's the best algorithm to check if a number is prime?Quora