Number prime test in JavaScript

Question

I m trying to complete the Codewars challenge that asks you to check if a number is a prime number  For whatever reason  my solution doesn t seem to work for the square of odd prime numbers  e g  9 returns true instead of false    x000D   x000D  function isPrime num       if  num     2        return true      else if  num  gt  1        for  var i   2  i  lt  num  i             if  num   i     0            return true          else if  num     i   i            return false         else           return false                    else       return false          console log isPrime 121    x000D   x000D   x000D   P s  I included that second else if statement because I was trying to solve the problem

User · Answer

Cool version   const isPrime   n   gt       Array n  keys    slice 2  map i   gt    n i   includes true   amp  amp    0 1  includes n

User · Answer

function isPrime num            if num  lt  2  return false          for  var i   2  i  lt   num 2  i                  if num i  0                  return false                    return true          If we want the prime number between two number we have to add this code only  for var i   0  i  lt  100  i             if isPrime i               console log i

User · Answer

I think a better way to find a prime number is with this logic    x000D   x000D  var p prompt  input numeric value   10       input your number  x000D  for j 2 j lt p j      x000D    if isPrimes j     x000D      document write j           for output the value x000D         end if x000D      end for loop x000D  function isPrimes n    x000D    var primes   true    let prime is true x000D    for  i 2 i lt n i      x000D      if n i  0    x000D        primes  false     return prime is false x000D        break     break the loop x000D          end if inner  x000D        end inner loop x000D    return primes     return the prime true or false x000D      end the function x000D   x000D   x000D

User · Answer

This will cover all the possibility of a prime number    order of the last 3 if statements is important      function isPrime num         if  num  0    num  1  return false      if  num  2    num  3   return true       if  num   Math sqrt num   0   return false      for  let i 2 i lt  Math floor Math sqrt num   i    if   num   i  0   return false      if   num   num - 1    24    0  return true

User · Answer

I think this question is lacking a recursive solution    x000D   x000D     Preliminary screen to save our beloved CPUs from unneccessary labour x000D   x000D  const isPrime   n   gt    x000D    if  n     2    n     3  return true  x000D    if  n  lt  2    n   2     0  return false  x000D   x000D    return isPrimeRecursive n   x000D    x000D   x000D     The recursive function itself  tail-call optimized  x000D     Iterate only over odd divisors  there s no point to iterate over even ones   x000D    x000D  const isPrimeRecursive    n  i   3  limit   Math floor Math sqrt n      gt     x000D    if  n   i     0  return false  x000D    if  i  gt   limit  return true     Heureka  we have a prime here  x000D    return isPrimeRecursive n  i    2  limit   x000D    x000D   x000D     Usage example x000D   x000D  for  i   0  i  lt   50  i      x000D    console log    i  is   isPrime i     a     not a    prime    x000D    x000D   x000D   x000D    This approach have it s downside     since browser engines are  written 11 2018  still not TC optimized  you d probably get a literal stack overflow error if testing primes in order of tens lower hundreds of millions or higher  may vary  depends on an actual browser and free memory

User · Answer

One of the shortest version  isPrime  n   gt     Array n-2   map    i   gt i 2  filter i  gt n i  0  length  0

User · Answer

x000D   x000D  function isPrime n   x000D   if  isNaN n      isFinite n     n 1    n lt 2    x000D    return false  x000D     x000D   x000D   if  n 2  0   x000D    return  n  2   x000D     x000D   x000D   var sqrt   Math sqrt n   x000D   for  var i   3  i  lt  sqrt  i  2    x000D    if n i    0   x000D     return false  x000D      x000D     x000D    x000D   return true  x000D    x000D   x000D   x000D

User · Answer

This answer is based on the answer by Ihor Sakaylyuk  But instead of checking for all numbers  I am checking only the odd numbers  Doing so I reduced the time complexity of the solution to O sqrt n  2     x000D   x000D  function isPrime num    x000D   if  num  gt  2  amp  amp  num   2     0  return false  x000D   for  var i   3  i  lt  Math sqrt num   i    2    x000D    if  num   i     0  return false  x000D     x000D   return num  gt  1  x000D    x000D   x000D   x000D

User · Answer

You can try this one    x000D   x000D  function isPrime num   x000D       x000D         Less than or equal to 1 are not prime x000D      if  num lt  1  return false  x000D       x000D         2 and 3 are prime  so no calculations x000D      if  num  2    num  3   return true   x000D       x000D         If mod with square root is zero then its not prime  x000D      if  num   Math sqrt num   0   return false  x000D       x000D         Run loop till square root x000D      for let i   2  sqrt   Math sqrt num   i  lt   sqrt  i      x000D       x000D             If mod is zero then its not prime x000D          if num   i     0  return false   x000D        x000D       x000D         Otherwise the number is prime x000D      return true  x000D       x000D      x000D      x000D     for let i -2  i  lt   35  i       x000D      console log    i  is  isPrime i           not   prime    x000D       x000D   x000D   x000D

User · Answer

function isPrime num        var prime   num    1      for var i 2  i lt num  i              if num   i    0                prime   false              break                      return prime      DEMO

User · Answer

This is how I d do it   function isPrime num      if num  lt  2  return false    if num    2  return true    for var i   2  i  lt  num  i          if num   i     0  return false        return true

User · Answer

function isPrimeNumber n      for  var i   2  i  lt  n  i         i will always be less than the parameter so the condition below will never allow parameter to be divisible by itself ex   7   7   0  which would return true     if n   i     0  return false     when parameter is divisible by i  it s not a prime number so return false       return n  gt  1     otherwise it s a prime number so return true  it also must be greater than 1  reason for the n  gt  1 instead of true     console log isPrimeNumber 1        returns false console log isPrimeNumber 2        returns true console log isPrimeNumber 9        returns false console log isPrimeNumber 11       returns true

User · Answer

function value       var primeArray           for var i   2  i  lt   value  i              if  i     2      i     3      i     5      i     7                 primeArray push i                       else if  i   2     0   amp  amp   i   3     0   amp  amp   i   5     0   amp  amp   i   7     0                   primeArray push i                                 console log primeArray     100

User · Answer

you can use below code in javascript for checking number is prime or not  It will reduce no of iteration and get the result fast   function testPrime num            var isPrime   true          if  num  gt   2                if num    2    num    3                  isPrime   true                            else if  num   2    0                    isPrime   false                            else                   for  i   3  i  lt   Math floor Math sqrt num    i    2                        if  num   i    0                            isPrime   false                          break                                                                          else               isPrime   false                    return isPrime            testPrime 21  false

User · Answer

x000D   x000D     A list prime numbers x000D   x000D  function  Prime number     x000D    const infinit    number  amp  amp  number     0  x000D    const re                 1       x000D    let actual   1  x000D    x000D    while  infinit    number--     x000D        if  re test  1  repeat actual      true  yield actual  x000D        actual   x000D       x000D     x000D   x000D  let     primers    Prime 101     Example x000D  console log primers   x000D   x000D   x000D

User · Answer

As simple as possible   function isPrime num      for var i   2  i  lt  num  i        if num   i     0  return false    return num  gt  1      With the ES6 syntax   const isPrime   num   gt      for let i   2  i  lt  num  i        if num   i     0  return false    return num  gt  1      You can also decrease the complexity of the algorithm from O n  to O sqrt n   if you run the loop until square root of a number   const isPrime   num   gt        for let i   2  s   Math sqrt num   i  lt   s  i            if num   i     0  return false       return num  gt  1

User · Answer

This one is I think more efficient to check prime number     function prime num    if num    1  return true   var t   num   2   var k   2   while k  lt   t       if num   k    0          return false      else      k               return true    console log prime 37

User · Answer

It looks like your first if statement within the first  if  statement within the for loop  Since if num   9 and i   2  9   i     0 but 9 is not prime since on the next iteration where i   3  9   i     0   Here would be my answer to that question   var isPrime   function n      if typeof n      number     n  lt   1    n   1     0       return false        for var i   2  i  lt   Math sqrt n   i    1       if n   i     0         return false              return true       The first if statement catches the edge cases  The for loop then checks from 2 up to the square root of n because of the mathematical property where no number has both of its factors greater than the square root of that number   Hope this helps

User · Answer

This calculates square differently and skips even numbers  const isPrime    n    gt      if  n  lt   1  return false    if  n     2  return true    if  n   2     0  return false      goto square root of number   for  let i   3  s   n    0 5  i  lt  s  i    2        if  n   i    0  return false        return true

User · Answer

Prime numbers are of the form 6f    1  excluding 2 and 3 where f is any integer   function isPrime number          if  number  lt   1     return false         The check for the number 2 and 3    if  number  lt   3     return true      if  number 2    0    number 3    0     return false      for  var i 5  i i lt  number  i i 6             if  number i    0    number  i 2     0         return false           return true       Time Complexity of the solution  O sqrt n

User · Answer

Why are you trying to use loops   Iterating is such a waste of computing power here         This can be done using math    function isPrime num        if   num   1  amp  amp  num 3    0  amp  amp  num 5    0  amp  amp  num 7    0  amp  amp  num 9    0  amp  amp  num 11    0  amp  amp  Math sign num     1  amp  amp  Math round num     num             if    num-1  6    0     num 1  6    0                 return true                      no need for else statement since if true  then will do return     return num  11  x  9  num  5  num  3  num  2     will return T F      Steps    Check if the number is divisible by 5  evenly  Check if the number is positive  negative numbers are not prime  Check if the number is a whole number  5 236 by rule not prime  Check if the number    1 is divisible by 6  evenly  For more information check out 3Blue1Brown s Video Check if the number is 2  3  9 or 11  outliers with the rule  Check if the number is 7 or 5  due to attempt at false-positive reduction    Always try to do the mathematical way  rather than iterating over loops  Math is almost always the most efficient way to do something  Yes  this equation might be confusing    However  we don t need much readability when it comes to checking if something is prime or not    It likely isn t going to need to be maintained by future code editors   EDIT  Optimized code version   function isPrime x 0        const m   Math      return  x 3  0 amp  amp x 5  0 amp  amp x 7  0 amp  amp x 9  0 amp  amp x 11  0 amp  amp x  1 amp  amp m sign x  m round x   x amp  amp       x-1  6        x 1  6     x  11  x  9  x  7  x  5  x  3  x  2      EDIT  As it turns out    there s more to do with false-positive detection  because they re randomly distributed  at least seemingly  so the  -1  6 stuff really isn t going to work for everything    But I m definitely on to something here

User · Answer

Simple version   function isPrime num        if  num  lt   1             return false        else           for  var i   2  i  lt  num  i                  if  num   i     0                    return false                                   return true             console log isPrime 9

User · Answer

function isPrime num       returns boolean   if  num  lt   1  return false     negatives   if  num   2    0  amp  amp  num  gt  2  return false     even numbers   const s   Math sqrt num      store the square to loop faster   for let i   3  i  lt   s  i    2       start from 3  stop at the square  increment in twos       if num   i     0  return false     modulo shows a divisor was found       return true    console log isPrime 121     Thanks to Zeph for fixing my mistakes

User · Answer

I would do it like this  const isPrime    num    gt  num  lt  10    2  3  5  7  includes num      2  3  5  7  some i   gt    num   i

User · Answer

Using Ticked solution Ihor Sakaylyuk  const isPrime   num   gt            for let i   2  s   Math sqrt num   i  lt   s  i                if num   i     0  return false           return num     1  amp  amp  num     0      Gives in console     isPrime  -100     true   const isPrime   num   gt         if not is number num return false    if  num  lt  2  return false    for let i   2  s   Math sqrt num   i  lt   s  i              if num   i     0  return false        return true     Gives in console     isPrime  1     false      isPrime  100     false      isPrime  -100     false   First 6 primes   2 3 5 7 11 13       isPrime  1     false      isPrime  2     true    Prime 1      isPrime  3     true    Prime 2      isPrime  4     false      isPrime  5     true    Prime 3      isPrime  6     false      isPrime  7     true    Prime 4      isPrime  8     false      isPrime  9     false      isPrime  10     false      isPrime  11     true    Prime 5      isPrime  12     false      isPrime  13     true    Prime 6

User · Answer

My Solution    x000D   x000D  function isPrimeNumber number   x000D    if number  lt   1  return false  x000D    if number  lt   3  return true  x000D    for let i   2  i  lt  9  i      x000D      if number     i  continue  x000D      if number   i     0   return false  x000D        x000D    return true  x000D    x000D   x000D  for let i   0  i  lt   100  i     x000D    if  isPrimeNumber i   console log i   x000D    x000D   x000D   x000D

User · Answer

A small suggestion here  why do you want to run the loop for whole n numbers   If a number is prime it will have 2 factors  1 and number itself   If it s not a prime they will have 1  number itself and more  you need not run the loop till the number  may be you can consider running it till the square root of the number   You can either do it by euler s prime logic  Check following snippet   function isPrime num      var sqrtnum Math floor Math sqrt num        var prime   num    1      for var i 2  i lt sqrtnum 1  i         sqrtnum 1         if num   i    0                prime   false              break                      return prime      Now the complexity is O sqrt n    For more information Why do we check up to the square root of a prime number to determine if it is prime   Hope it helps

User · Answer

You are trying to check too much conditions  just one loop is required to check for a prime no   function isPrime num   if num  2   return true  for i 2 i lt Math sqrt num  i       mathematical property-no number has both of its factors greater than the square root    if num   i  0   return false     otherwise it s a prime no    return true      You have to consider every no  a prime no  unless it is divisible by some no  less than or equal to the square root   Your solution has got a return statement for every case thus it stops execution before it should It doesn t check any number more than once It gives wrong answer for multiple cases-- 15 35   in fact for every no  that is odd

User · Answer

i think the easiest way to get it and faster is  x000D   x000D  function isPrime num      for var i   2  i  lt  Math sqrt num   i            if num   i     0             return false              return num  gt  1          console log isPrime 9   x000D   x000D   x000D

User · Answer

IhorSakaylyuk s answer can be improved further down to O sqrt n 2   by skipping all of the even numbers except 2  const isPrime   number   gt        if num   2     0  amp  amp  number     2  return false     for let i   3  s   Math sqrt num   i  lt   s  i    2          if num   i     0  return false       return num  gt  1     You can also use the npm package pial

User · Answer

very simple  const isPrime   num   gt      for  var i   2  i  lt  num  i    if  num   i    0  return false    return num  gt   2

User · Answer

function isAPrimeNumber num        var counter   0         loop will go k equals to  num      for  k   1  k  lt   num  k              check if the num is divisible by itself and 1              modulus gives the reminder of the value  so if it gives the reminder  0  then it is divisible by the value        if  num   k    0               increment counter value 1          counter    counter    1                       if the value of the  counter is 2  then it is a  prime number      A prime number is exactly divisible by 2 times only  itself and 1     if  counter    2         return num     is a Prime Number       else      return num     is nota Prime Number             Now call isAPrimeNumber   function by passing a value   var resp   isAPrimeNumber 5   console log resp     Output    5 is a Prime Number

User · Answer

The only even prime number is 2  so we should exclude even numbers from the loop   function isPrime a        if  a  lt  2  return false      if  a  gt  2            if  a   2    0  return false          for  let x   3  x  lt   Math sqrt a   x    2                if  a   x    0  return false                      return true

User · Answer

Following code uses most efficient way of looping to check if a given number is prime    function checkPrime number           if  number  2    number  3        return true       if number lt 2   number   2   0           return false           else          for  let index   3  index  lt   Math sqrt number   index index 2                if  number index   0                    return false                                           return true      First check rules out 2 and lesser numbers and all even numbers Using Math sqrt   to minimize the looping count Incrementing loop counter by 2  skipping all even numbers  further reducing loop count by half

User · Answer

This is a more reliable solution if you want to find n prime numbers   x000D   x000D  function findPrime n          const primes             loop1        for  let j   0  primes length  lt  n  j             loop2         for let i   2  i  lt  j  i             if j   i     0               continue loop1                          if j gt 1  primes push j                 console log primes                   findPrime 5   x000D   x000D   x000D

User · Answer

Might be useful for some people  An implementation of the Miller Rabin primality test  Works for all positive integers less than Number MAX SAFE INTEGER  Try on JSFiddle  https   jsfiddle net 4rxhas2o   let unsafeToSquare   Math floor Math sqrt Number MAX SAFE INTEGER    function addMod a  b  m         Returns  a   b    m    let sum   a   b    let result   sum   m    if  sum  lt  Number MAX SAFE INTEGER      return result    let signature     a   8     b   8     8    let sumMod   sum   8    for  let i   -2  i  lt   2    i        if   sumMod   i    8     signature          let ret   result   i        if  ret  gt  m          ret    result - m    i    prevent overflow        return ret              function mulMod a  b  m      if  m     0      return 0    let prod   a   b    if  prod  lt  Number MAX SAFE INTEGER      return prod   m    let y   0   let result   a    while  b  gt  1        if  b   2     0          result   addMod result  result  m         b    2       else         y   addMod result  y  m        result   addMod result  result  m         b    b - 1    2              return addMod result  y  m     function squareMod b  m         Computes  b   b   m     return mulMod b  b  m     function expModLargeB b  exponent  m      let y   1    while  exponent  gt  1        if  exponent   2     0          b   squareMod b  m         exponent    2       else         y   mulMod y  b  m        b   squareMod b  m         exponent    exponent - 1    2              return mulMod b  y  m     function expMod b  exponent  m      if  exponent     0      return 1    if  b  gt   unsafeToSquare    m  gt   unsafeToSquare        return expModLargeB b  exponent  m         let y   1    while  exponent  gt  1        if  exponent   2     0          b    b       b    m        exponent    2       else         y    b       b    b        y    m       b    m        exponent    exponent - 1    2              return  b   y    m    function  isPrimeTrialDivision p      let sqrtP   Math ceil Math sqrt p      for  let i   23  i  lt   sqrtP   1  i    2        if  p   i     0        return false        return true    function  isProbablePrimeMillerRabin p  base 2      let pm1   p - 1   let pm1div   pm1   let d  r   0    while  true        if  pm1div   2     0          pm1div    2        r         else         d   pm1div       break              let x   expMod base  d  p     if  x     1    x     pm1      return true    for  let i   0  i  lt  r - 1    i        x   squareMod x  p       if  x     pm1        return true        return false    function  isPrimeLarge p      let bases    if  p  lt  2047      bases    2    else if  p  lt  1373653      bases    2  3    else if  p  lt  9080191      bases    31  73    else if  p  lt  25326001      bases    2  3  5    else if  p  lt  3215031751      bases    2  3  5  7    else if  p  lt  4759123141      bases    2  7  61    else if  p  lt  1122004669633      bases    2  13  23  1662803    else if  p  lt  2152302898747      bases    2  3  5  7  11    else if  p  lt  3474749660383      bases    2  3  5  7  11  13    else if  p  lt  341550071728321      bases    2  3  5  7  11  13  17    else     bases    2  3  5  7  11  13  17  19  23      return bases every base   gt   isProbablePrimeMillerRabin p  base      let smallPrimes    2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223   function isPrime p      if   Number isInteger p     p  lt  2      return false       Test for small primes   for  let i   0  i  lt  smallPrimes length    i        let prime   smallPrimes i       if  p     prime        return true     if  p   prime     0        return false        if  p  lt  150        return  isPrimeTrialDivision p      else       return  isPrimeLarge p          const tests    1  2  3  10  100  100019  10000000019  100000000003  10000000000037  let start   performance now    tests forEach test   gt        console log    test  is    isPrime test     quot  quot     quot not  quot   prime       let end   performance now   console log  quot Tests completed in  quot     end - start     quot  ms  quot

[javascript] Number prime test in JavaScript

Examples related to javascript