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).
function isPrime(num) { if (num === 2) { return true; } else if (num > 1) { for (var i = 2; i < 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));P.s. I included that second else/if statement because I was trying to solve the problem.
546 Answers
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; } 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
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.
2Cool version:
const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n) 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))
0function 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 // 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);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); 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).
function isPrime(num) { var prime = num != 1; for(var i=2; i<num; i++) { if(num % i == 0) { prime = false; break; } } return prime; } very simple
const isPrime = num => { for (var i = 2; i < num; i++) if (num % i == 0) return false; return num >= 2; } One of the shortest version
isPrime=(n)=>[...Array(n-2)].map((_,i)=>i+2).filter(i=>n%i==0).length==0 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
5Since 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.
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 functionYou 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`); }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; }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.
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.
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.") 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<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.
1It 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!
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 <= t) { if(num % k == 0) { return false } else { k++; } } return true; } console.log(prime(37)) Simple version:
function isPrime(num) { if (num <= 1) { return false; } else { for (var i = 2; i < num; i++) { if (num % i === 0) { return false; } } return true; } } console.log(isPrime(9)); 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; } (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)); 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 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); } 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
function isPrime(n){ if (isNaN(n) || !isFinite(n) || n%1 || n<2) { return false; } if (n%2==0){ return (n==2); } var sqrt = Math.sqrt(n); for (var i = 3; i < sqrt; i+=2) { if(n%i == 0){ return false; } } return true; }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); }
