John Ozenua
John Ozenua

Reputation: 1091

Check Number prime in JavaScript

Check Number prime in JavaScript

let inputValue= 7;
let isprime=inputValue==1? false:true;  //bcoz 1 is not prime

for(let i=2;i<inputValue;i++){
  inputValue%i==0? isprime*=false :isprime*=true;
};

alert(`${inputValue} is ${isprime? 'prime':'not prime'} number`);

Upvotes: 92

Views: 415679

Answers (30)

Ovinus Real
Ovinus Real

Reputation: 568

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 < Number.MAX_SAFE_INTEGER)
    return result

  let signature = ((a % 8) + (b % 8)) % 8

  let sumMod = sum % 8

  for (let i = -2; i <= 2; ++i) {
    if ((sumMod + i) % 8 === signature) {
      let ret = result + i

      if (ret > 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 < Number.MAX_SAFE_INTEGER)
    return prod % m

  let y = 0
  let result = a

  while (b > 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 > 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 >= unsafeToSquare || m >= unsafeToSquare) {
    return expModLargeB(b, exponent, m)
  }

  let y = 1

  while (exponent > 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 _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 < r - 1; ++i) {
    x = squareMod(x, p)

    if (x === pm1)
      return true
  }

  return false
}

function _isPrimeLarge(p) {
  let bases

  if (p < 2047)
    bases = [2]
  else if (p < 1373653)
    bases = [2, 3]
  else if (p < 9080191)
    bases = [31, 73]
  else if (p < 25326001)
    bases = [2, 3, 5]
  else if (p < 3215031751)
    bases = [2, 3, 5, 7]
  else if (p < 4759123141)
    bases = [2, 7, 61]
  else if (p < 1122004669633)
    bases = [2, 13, 23, 1662803]
  else if (p < 2152302898747)
    bases = [2, 3, 5, 7, 11]
  else if (p < 3474749660383)
    bases = [2, 3, 5, 7, 11, 13]
  else if (p < 341550071728321)
    bases = [2, 3, 5, 7, 11, 13, 17]
  else
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]


  return bases.every(base => _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 < 2)
    return false

  // Test for small primes
  for (let i = 0; i < smallPrimes.length; ++i) {
    let prime = smallPrimes[i]

    if (p === prime)
      return true
    if (p % prime === 0)
      return false
  }

  if (p <= 49729) { // 223*223
    return true;
  }
  else {
    return _isPrimeLarge(p)
  }
}


const tests = [1, 2, 3, 10, 100, 100019, 10000000019, 100000000003, 10000000000037]
let start = performance.now()

tests.forEach(test => {
    console.log(`${test} is ${ isPrime(test) ? "" : "not " }prime`)
})

let end = performance.now()
console.log("Tests completed in " + (end - start) + " ms.")

Upvotes: 1

Serhiy Gavrylov
Serhiy Gavrylov

Reputation: 61

/**
* Preliminary checks:
*
* Checks whether the number n is less than or 
* equal to 1. If so, the function returns an 
* error.
* It checks whether n is equal to 2 or 3. If it 
* is, the number is considered prime.
* Checking for divisibility by 2 and 3:
*
* It checks whether the number n is divisible by 
* 2 or 3. If it is divisible, the number is said 
* to be composite.
* Checking for divisibility by 6k ± 1:
*
* An optimised approach is used to check 
* division by numbers of the form 6k ± 1 (except 
* 2 and 3), which reduces the number of 
* divisions.
*/


function speedTest(n) {
    if (n <= 1) {
        return 'error';
    }

    if (n == 2 || n == 3) {
        return 'Prime';
    }

    if (n % 2 == 0 || n % 3 == 0) {
        return 'Composite';
    }

    //the divisors of a number cannot be greater than its square root.
    const sqrt = Math.sqrt(n);

    for (let i = 5; i <= sqrt; i += 6) {
        if (n % i == 0) {
            return 'Composite';
        }
    }

    for (let i = 7; i <= sqrt; i += 6) {
        if (n % i == 0) {
            return 'Composite';
        }
    }

    return 'Prime';
}

Upvotes: 0

Ihor Sakailiuk
Ihor Sakailiuk

Reputation: 6078

Time complexity: O(sqrt(n))

Space complexity: O(1)

const isPrime = num => {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++) {
        if(num % i === 0) return false;
    }
    return num > 1;
}

Upvotes: 270

Andrew Rusanov
Andrew Rusanov

Reputation: 85

I would do it like this:

const isPrime = (num) => num < 10 ? [2, 3, 5, 7].includes(num) : ![2, 3, 5, 7].some(i => !(num % i));

UPDATE (thx to @lakscastro):

export const isPrime = n => n <= 1 ? false : !Array.from(new Array(n), (el, i) => i + 1)
  .filter(x => x > 1 && x < n)
  .find(x => n % x === 0);

Upvotes: 4

Richie Bendall
Richie Bendall

Reputation: 9242

Since Node.js 16, this is built-in:

import {checkPrimeSync as isPrime} from 'node:crypto';

console.log(isPrime(13));
//=> true

Otherwise, @IhorSakaylyuk's answer can be improved further by skipping even numbers:

function isPrime(number) {
    if((number % 2 === 0 && number !== 2) || number <= 1) {
        return false;
    }

    const limit = Math.floor(Math.sqrt(number));

    for(let index = 3; index <= limit; index += 2) {
        if (number % index === 0) {
            return false;
        }
    }

    return true;
}

I also created a npm package with this function.

Upvotes: 5

vitaly-t
vitaly-t

Reputation: 25950

The following implementation is faster than in all the previous answers, that's why I'm adding it.

The code below is from my prime library:

/**
 * Maximum prime number that can be generated in JavaScript,
 * using the standard 'number' type (53-bit of integer range).
 */
const maxPrime = 9_007_199_254_740_881;

const dividers = [
    0, 2, 6, 8, 12, 18, 20, 26, 30, 32, 36, 42, 48, 50, 56, 60, 62, 68, 72, 
    78, 86, 90, 92, 96, 98, 102, 110, 116, 120, 126, 128, 132, 138, 140, 146,
    152, 156, 158, 162, 168, 170, 176, 180, 182, 186, 188, 198, 200
];

function isPrime(x: number): boolean {
    if (isNaN(x) || x < 2 || x > maxPrime || x % 1) {
        return false;
    }
    if (x % 2 === 0) return x === 2;
    if (x % 3 === 0) return x === 3;
    if (x % 5 === 0) return x === 5;
    if (x % 7 === 0) return x === 7;
    const m = Math.sqrt(x);
    for (let i = 11; i <= m; i += 210) {
        for (const a of dividers) {
            if (x % (i + a) === 0) {
                return i + a === x;
            }
        }
    }
    return true;
}

On my machine, it can verify the first million numbers in 217ms.

Upvotes: 1

vasanth.v
vasanth.v

Reputation: 213

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).

function isPrime(num) {
    if (num > 2 && num % 2 === 0) return false;
    for (var i = 3; i < Math.sqrt(num); i += 2) {
        if (num % i === 0) return false;
    }
    return num > 1;
}

Upvotes: 0

Nazariy
Nazariy

Reputation: 417

Three times faster then regular method:

function isPrime (num){
    if (num === 1){
        return false;
    }
    if(num === 2 || num === 3){
        return true;
    }
    if((num % 2 !== 0) && (num % 3 !== 0)){
        let k = 1;
        const numSqrt = Math.sqrt(num);
        if(( 6 * k - 1 ) > numSqrt){
            return true;
        } else {
            while( ( 6 * k - 1 ) <= numSqrt ){
                if(num % (6 * k - 1) !== 0 && num % (6 * k + 1) !== 0){
                return true;
            }
            k++;
        }
        return false;
      }
  }
  return false;
}
console.log(isPrime(29))

Upvotes: 0

Tomachi
Tomachi

Reputation: 1775

function isPrime(num) { // returns boolean
  if (num <= 1) return false; // negatives
  if (num % 2 == 0 && num > 2) return false; // even numbers
  const s = Math.sqrt(num); // store the square to loop faster
  for(let i = 3; i <= 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.

Upvotes: 19

RRD
RRD

Reputation: 19

This is a more reliable solution if you want to find n prime numbers.

function findPrime(n) {
      const primes = [];
      loop1:
      for (let j = 0; primes.length < n; j++) {
       loop2:
       for(let i = 2; i < j; i++){
        if(j % i === 0){
            continue loop1;
        }
      }
      if(j>1) primes.push(j);
      }
      console.log(primes);
    }
     
    findPrime(5);

Upvotes: 0

VnoitKumar
VnoitKumar

Reputation: 1426

My Solution,

function isPrimeNumber(number){
  if(number <= 1) return false;
  if(number <= 3) return true;
  for(let i = 2; i < 9; i++) {
    if(number === i) continue;
    if(number % i === 0 ) return false;
  }  
  return true;
}

for(let i = 0; i <= 100; i++){
  if (isPrimeNumber(i)) console.log(i);
}

Upvotes: -1

Ashikur Rahman
Ashikur Rahman

Reputation: 78

One of the shortest version

isPrime=(n)=>[...Array(n-2)].map((_,i)=>i+2).filter(i=>n%i==0).length==0

Upvotes: -1

H S W
H S W

Reputation: 7164

Prime numbers are of the form 6f ± 1, excluding 2 and 3 where f is any integer

 function isPrime(number)
 { 
   if (number <= 1)
   return false;

   // The check for the number 2 and 3
   if (number <= 3)
   return true;

   if (number%2 == 0 || number%3 == 0)
   return false;

   for (var i=5; i*i<=number; i=i+6)
   {
      if (number%i == 0 || number%(i+2) == 0)
      return false;
   }

   return true;
 }

Time Complexity of the solution: O(sqrt(n))

Upvotes: 14

Nikhil Mahirrao
Nikhil Mahirrao

Reputation: 3721

You can try this one

function isPrime(num){
   	
    // Less than or equal to 1 are not prime
    if (num<=1) return false;
    
    // 2 and 3 are prime, so no calculations
    if (num==2 || num==3 ) return true; 
    
    // If mod with square root is zero then its not prime 
    if (num % Math.sqrt(num)==0 ) return false;
    
    // Run loop till square root
    for(let i = 2, sqrt = Math.sqrt(num); i <= sqrt; i++) {
    
        // If mod is zero then its not prime
        if(num % i === 0) return false; 
    }
    
    // Otherwise the number is prime
    return true;
   }
   
   
   for(let i=-2; i <= 35; i++) { 
   	console.log(`${i} is${isPrime(i) ? '' : ' not'} prime`);
   }

Upvotes: 0

John Griffiths
John Griffiths

Reputation: 3433

Using Ticked solution Ihor Sakaylyuk

const isPrime = num => {
        for(let i = 2, s = Math.sqrt(num); i <= s; i++)
            if(num % i === 0) return false; 
        return num !== 1 && num !== 0;
}

Gives in console

isPrime( -100 ) true

const isPrime = num => {
  // if not is_number num return false

  if (num < 2) return false

  for(let i = 2, s = Math.sqrt(num); i <= 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

Upvotes: 0

HynekS
HynekS

Reputation: 3327

I think this question is lacking a recursive solution:

// Preliminary screen to save our beloved CPUs from unneccessary labour

const isPrime = n => {
  if (n === 2 || n === 3) return true;
  if (n < 2 || n % 2 === 0) return false;

  return isPrimeRecursive(n);
}

// The recursive function itself, tail-call optimized.
// Iterate only over odd divisors (there's no point to iterate over even ones).
 
const isPrimeRecursive = (n, i = 3, limit = Math.floor(Math.sqrt(n))) => {	
  if (n % i === 0) return false;
  if (i >= limit) return true; // Heureka, we have a prime here!
  return isPrimeRecursive(n, i += 2, limit);
}

// Usage example

for (i = 0; i <= 50; i++) {
  console.log(`${i} is ${isPrime(i) ? `a` : `not a` } prime`);
}

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).

Upvotes: 3

Srikrushna
Srikrushna

Reputation: 4965

function isPrime(num) {
        if(num < 2) return false;
        for (var i = 2; i <= 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 < 100; i++){
        if(isPrime(i))
            console.log(i);
    }

Upvotes: -1

Gufran Hasan
Gufran Hasan

Reputation: 9411

function isAPrimeNumber(num){
     var counter = 0;
     //loop will go k equals to $num
     for (k = 1; k <= 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

Upvotes: 0

Sumon Ahmed
Sumon Ahmed

Reputation: 7

I think a better way to find a prime number is with this logic:

var p=prompt("input numeric value","10"); // input your number 
for(j=2;j<p;j++){ 
  if(isPrimes(j)){ 
    document.write(j+", "); // for output the value
  } // end if
}// end for loop
function isPrimes(n) {
  var primes = true;// let prime is true
  for (i=2;i<n;i++) {
    if(n%i==0) {
      primes= false; // return prime is false
      break; // break the loop
    }// end if inner 
  }// end inner loop
  return primes; // return the prime true or false
}// end the function

Upvotes: -1

tyroD
tyroD

Reputation: 1

(function(value){
    var primeArray = [];
    for(var i = 2; i <= value; i++){ 
        if((i === 2) || (i === 3) || (i === 5) || (i === 7)){ 
            primeArray.push(i);
        }
          else if((i % 2 !== 0) && (i % 3 !== 0) && (i % 5 !== 0) && (i % 7 !== 0)){ 
              primeArray.push(i);
          }
        } 
       console.log(primeArray);
}(100));

Upvotes: -1

Behnam
Behnam

Reputation: 6459

very simple

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

Upvotes: 0

Harrison Kamau
Harrison Kamau

Reputation: 322

This is how I'd do it:

function isPrime(num) {
  if(num < 2) return false;
  if(num == 2) return true;
  for(var i = 2; i < num; i++) {
    if(num % i === 0) return false;
  }
  return true;
}

Upvotes: -1

Sergio
Sergio

Reputation: 1364

Cool version:

const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n)

Upvotes: 6

Geeky
Geeky

Reputation: 7496

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<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

Upvotes: 31

N.Tayel
N.Tayel

Reputation: 1

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< Math.floor(Math.sqrt(num));i++) if ( num % i==0 ) return false;
    if ((num * num - 1) % 24 == 0) return true;        
   }

Upvotes: -1

Mary Pieroszkiewicz
Mary Pieroszkiewicz

Reputation: 361

function isPrimeNumber(n) {
  for (var i = 2; i < 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 > 1; // otherwise it's a prime number so return true (it also must be greater than 1, reason for the n > 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

Upvotes: 7

RASHID HAMID
RASHID HAMID

Reputation: 53

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 >= 2) {
            if(num == 2 || num == 3){
               isPrime = true;
            }
            else if (num % 2 == 0) {
                isPrime = false;
            }
            else {
                for (i = 3; i <= Math.floor(Math.sqrt(num)); i += 2) {
                    if (num % i == 0) {
                        isPrime = false;
                        break;
                    }
                }
            }
        }
        else {
            isPrime = false;
        }
        return isPrime;
    }

//testPrime(21) false

Upvotes: 2

arius
arius

Reputation: 67

// A list prime numbers

function* Prime(number) { 
  const infinit = !number && number !== 0;
  const re = /^.?$|^(..+?)\1+$/;  
  let actual = 1;
 
  while (infinit || number-- ) {
      if(!re.test('1'.repeat(actual)) == true) yield actual;
      actual++
  };
};

let [...primers] = Prime(101); //Example
console.log(primers);

Upvotes: 3

rodaan
rodaan

Reputation: 1

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 <= 1 || n % 1 !== 0){
    return false;
  }
  for(var i = 2; i <= 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!

Upvotes: -1

Sajeetharan
Sajeetharan

Reputation: 222657

function isPrime(num) {
    var prime = num != 1;
    for(var i=2; i<num; i++) {
        if(num % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

DEMO

Upvotes: 4

Related Questions