Detecting prime numbers in JavaScript

Question

Can someone please give me guidance on getting the primenumbers here? This is homework so I don't want the answer but some pointers would be greatly appreciated. It's really annoying me :(

I think I'm close. But this problems I have are number 25 and 35. These are not prime but this function is returning them

var getPrimeNumber = function(n) {
    if(n === 1) return "";
    else if(n == 2) return 2;
    else if(n == 3) return 3;
    else { 
        for(i=Math.floor(Math.sqrt(n)); i>=2; i--){
            //console.log(i);//maybe another var in here? 
            if(n%i !==0 && n%2 !==0 && n%3 !== 0)
                return n; // 25/Math.sqrt(25) will be equal to zero this is what gives me 25 !!!   
        } 
    }
};

Answer 1

this should be fastest but it may should up with pseudo primes.

function isPrimeFermetWay(num) {
    if (num < 2) return false;
    if (num === 2) return true;
    if (Math.pow(2, num - 1) % num === 1) return true;
    return false;
}

function isPrimeFermetWay(num) {
    if (num < 2) return false;
    if (num === 2) return true;
    if (2**(num - 1) % num === 1) return true;
    return false;
}

the same version shoud work better in optimised manner

function isPrimeFermetWay(num) {
    if (num < 2) return false;
    if ((num === 2 || num === 3 || num === 5 || num === 7)) return true;
    if (num === 1 || ((num > 7) && (num % 2 === 0 || num % 3 === 0 || num % 5 === 0 || num % 7 === 0))) return false;

    if (2**(num - 1) % num === 1) return true;
    return false;
}

If a ** (n−1) (modulo n) is 1 but n is not prime. If a ** (n−1) (modulo n) is 1 but n is not prime, then n is called a pseudoprime to base a. But here is a counter. example: if n = 341 and a = 2, then 2 ** 340 mod n === 1. even though 341 = 11x31 is composite. In fact, 341 is the smallest pseudoprime base 2. There are only 21853 pseudoprimes base 2 that are less than 2.5×1010. This means that, for n up to 2.5×1010, if 2 ** n−1 (modulo n) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes.

Some composite numbers (Carmichael numbers) have the property that an − 1 is 1 (modulo n) for every a that is coprime to n. The smallest example is n = 561 = 3x11x17, for which a ** 560 is 1 (modulo 561) for all a coprime to 561.

Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographic algorithm.

https://en.wikipedia.org/wiki/Primality_test#Fermat_primality_test

function isPrimeFermetWay(num) {
  if (num < 2) return false;
  if (num === 2) return true;
  if (Math.pow(2, num - 1) % num === 1) return true;
  return false;
}

console.log("27 is a prime number: ", isPrimeFermetWay(27)) 
console.log("30 is a prime number: ", isPrimeFermetWay(30)) 
console.log("55 is a prime number: ", isPrimeFermetWay(55)) 
console.log("2 is a prime number: ", isPrimeFermetWay(2)) 
console.log("13 is a prime number: ", isPrimeFermetWay(13)) 
console.log("71 is a prime number: ", isPrimeFermetWay(71)) 
console.log("23 is a prime number: ", isPrimeFermetWay(23)) 
console.log("19 is a prime number: ", isPrimeFermetWay(19)) 

function isPrimeFermetWay(num) {
  if (num < 2) return false;
  if (num === 2) return true;
  if (2**(num - 1) % num === 1) return true;
  return false;
}

console.log("27 is a prime number: ", isPrimeFermetWay(27)) 
console.log("30 is a prime number: ", isPrimeFermetWay(30)) 
console.log("55 is a prime number: ", isPrimeFermetWay(55)) 
console.log("2 is a prime number: ", isPrimeFermetWay(2)) 
console.log("13 is a prime number: ", isPrimeFermetWay(13)) 
console.log("71 is a prime number: ", isPrimeFermetWay(71)) 
console.log("23 is a prime number: ", isPrimeFermetWay(23)) 
console.log("19 is a prime number: ", isPrimeFermetWay(19)) 

function isPrimeFermetWay(num) {
  if (num < 2) return false;
  if ((num === 2 || num === 3 || num === 5 || num === 7)) return true;
  if (num === 1 || ((num > 7) && (num % 2 === 0 || num % 3 === 0 || num % 5 === 0 || num % 7 === 0))) return false;

  if (2**(num - 1) % num === 1) return true;
  return false;
}


console.log("27 is a prime number: ", isPrimeFermetWay(27)) 
console.log("30 is a prime number: ", isPrimeFermetWay(30)) 
console.log("55 is a prime number: ", isPrimeFermetWay(55)) 
console.log("2 is a prime number: ", isPrimeFermetWay(2)) 
console.log("13 is a prime number: ", isPrimeFermetWay(13)) 
console.log("71 is a prime number: ", isPrimeFermetWay(71)) 
console.log("23 is a prime number: ", isPrimeFermetWay(23)) 
console.log("19 is a prime number: ", isPrimeFermetWay(19)) 

Answer 2

Here's the fastest way to calculate primes in JavaScript, based on the previous prime value.

function nextPrime(value) {
    if (value > 2) {
        var i, q;
        do {
             i = 3;
             value += 2;
             q = Math.floor(Math.sqrt(value));
             while (i <= q && value % i) {
                 i += 2;
             }
        } while (i <= q);
        return value;
    }
    return value === 2 ? 3 : 2;
}

Test

var value, result = [];
for (var i = 0; i < 10; i++) {
    value = nextPrime(value);
    result.push(value);
}
console.log("Primes:", result);

Output

Primes: [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]

It is very fast, because:

• It aligns the loop limit to an integer;
• It uses a shorter iteration loop, skipping even numbers.

It can give you the first 100,000 primes in about 130ms, or the first 1m primes in about 4 seconds.

2021 Update

In this day and age, we should be using ES6 generators for this:

// generates "n" primes that follow "startPrime";
function* nextPrimes(startPrime, n) {
    let value = startPrime, i = 0;
    while (i++ < n) {
        if (value > 2) {
            let k, q;
            do {
                k = 3;
                value += 2;
                q = Math.floor(Math.sqrt(value));
                while (k <= q && value % k) {
                    k += 2;
                }
            } while (k <= q);
        } else {
            value = value === 2 ? 3 : 2;
        }
        yield value;
    }
}

test:

const result = [...nextPrimes(1, 10)];
//=> [2,  3,  5,  7, 11, 13, 17, 19, 23, 29]

function* nextPrimes(startPrime, n) {
let value = startPrime, i = 0;
while (i++ < n) {
    if (value > 2) {
        let k, q;
        do {
            k = 3;
            value += 2;
            q = Math.floor(Math.sqrt(value));
            while (k <= q && value % k) {
                k += 2;
            }
        } while (k <= q);
    } else {
        value = value === 2 ? 3 : 2;
    }
    yield value;
}
}

const result = [...nextPrimes(1, 10)];

display('Primes: ' + result.join(', '));

function display(msg) {
   document.body.insertAdjacentHTML(
  'beforeend',
  '<p>' + msg + '</p>'
);
}

See also: My prime-lib library that works much faster.

Answer 3

I considered the following in my implementation: Prime numbers are "natural numbers" and it is possible for negative values to be prime numbers. This is a more definitive solution with input sanitation:

function isPrime(num) {
    //check if value is a natural numbers (integer)
    //without this check, it returns true
    if (isNaN(num) || num % 1 !== 0) {
        return false;
    }
    num = Math.abs(num); //*negative values can be primes
    if (num === 0 || num === 1) {
        return false;
    }
    var maxFactorNum = Math.sqrt(num);
    for (var i = 2; i <= maxFactorNum; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}

//checking anomalies
console.log(isPrime(1.22));
console.log(isPrime(1.44));
console.log(isPrime("string"));

console.log("All prime numbers from 1-1000:");
var arr = [];
for (var i = 1; i < 1000; i++) if (isPrime(i)) arr.push(i);
console.log(arr.join`, `);

I hope my answer proves to be more readable code that also uses best practices. For example, some answers leave the square root calculation in the loop causing the method to run that calculation on every loop.

Answer 4

I barely understand people's code, so here is mine (idk if they are not too clean but i think it's very easy to understand)

    function primeNum (x){
    const primeArray =[];

    for (var i = 1 ; i <= x ; i++){
        if (x % i === 0){
            primeArray.push(i)
        }
    }

    if (primeArray.length === 2){
        return "it's a prime boys"
    } else {
        return "it's not a prime sorry to say"
    }
}

the concept is simple, prime number is a number that only can divied by only 2 numbers and has modulo equal to 0 (x % i === 0). So if the primeArray has length more than 2 (more than 2 numbers), it's not a prime number.

i don't know what people says about my code, i need your advice guys. Best Regards.

Answer 5

Based on this page, this would be a method for determining if a number is a prime number:

function isPrime(number) {
    let start = 2;
    const limit = Math.sqrt(number);
    while (start <= limit) {
        if (number % start++ < 1) return false;
    }
    return number > 1;
}

In node.js it takes about 250Ms for determining the prime numbers between 2 and 100.000.

See also ...

[edit aug. 2021] A somewhat more efficient function. See this Stackblitz project

document.querySelector(`pre`).textContent = `Prime numbers < 100\n` +
  [...Array(100)]
  .map((v, i) => isPrime(i) ? i : 0)
  .filter(v => v > 0)
  .join(`\n`);

function isPrime(number) {
  const checkPrime = (nr, limit) => {
    for (let start = 3; start <= limit; start += 2) {
      if (0 === nr % start) {
        return false;
      }
    }

    return nr > 1;
  };

  return number === 2 || number % 2 !== 0 && checkPrime(number, Math.sqrt(number));
}

<pre></pre>

Answer 6

Try the below code. It checks if the number is prime and if it isn't it logs the number's lowest divisor. It is accurate for numbers with less than 17 digits (this theoretically would work for any number but the way JavaScript works means that this isn't true). You can try it out embedded into a website here: https://prime-number-checker-git-main.matt-destroyer.vercel.app/ Or in the snippet below.

function check() {
    function checkIfPrime(number) {
        if (number < 1) {
            i = 'less than zero or the number you entered was zero';
            return false;
        } else if (number < 2) {
            i = 'itself only';
            return false;
        } else if (number % 2 === 0) {
            i = 2;
            return false;
        } else if (number < 10) {
            if (number === 3) {
                return true;
            } else if (number === 5) {
                return true;
            } else if (number === 7) {
                return true;
            }else if (number === 9) {
                i = 3;
                return false;
            } 
        } else if (number % 3 === 0) {
            i = 3;
            return false;
        } else if (number % 5 === 0) {
            i = 5;
            return false;
        } else if (number % 7 === 0) {
            i = 7;
            return false;
        } else {
            i = 4;
            while (i * i < number) {
                if (number % i === 0) {
                    return false;
                }
                i += 2;
            }
            return true;
        }
    }
    let i = 0;
    let input = parseInt(prompt('Enter a number to check if it is prime:'));
    if (input < 0) {
        alert(input + ' is not a prime number. A prime number must be a positive integer.');
    } else if (input === "") {
        alert("You cannot check if 'BLANK' is prime.");
    } else if (input != Math.round(input)) {
        alert(input + ' is not a prime number. A prime number cannot be a decimal.');
    } else {
        let check = checkIfPrime(input);
        if (check === true) {
            alert(input + ' is a prime number.');
        } else {
            alert(input + ' is not a prime number. Its lowest divisor is ' + i + '.');
        }
    }
}
check();

Answer 7

This is my Answer

var isPrime = function (n) {
  if (n < 2) {
    return false;
  } else if (n === 2) {
    return true;
  }
  for (var i = 2; i < n; i++) {
    if (n%i === 0) {
      return false;
    } else if (i === n-1) {
      return true;
    }
  }
}
console.log(isPrime(7));

Answer 8

Here's a simple "sieve" for prime numbers, which can be easily understood, and although it is a naive approach (as opposed to sophisticated efficient prime number tests such as the AKS test), it is pretty fast (10000 numbers tested in < 1 sec). It stores the found prime numbers in the array prim[] and tests by using the modulo function (%):

The loop tests against already found prime numbers and exits if it is no prime number, i.e. if the modulo result is 0 (regard the expression i % prim[j])===0). Otherwise, it adds it to the list of found prime numbers.

Note that because the only even prime number is 2, the loop step is 2 rather then 1, because from 3 onwards there can't be any further even prime numbers.

var MaxNum = 10000;
var prim;

function Main() {
  MaxNum = GetMaxNum();
  prim = CalculatePrimes(MaxNum);
  CheckSome();
}

function CalculatePrimes(pMaxNum) {
  Console.WriteLine("Calculating until " + pMaxNum + "...");
  var _prim = [2];
  if (pMaxNum > 2) {
    for (var i = 3; i < pMaxNum; i += 2) {
      var is_prim = true;
      if (_prim.length > 0) {
        for (var j = 0; j < _prim.length; j++) {
          if ((i % _prim[j]) === 0) {
            is_prim = false;
            break;
          }
        }
      }
      if (is_prim) {
        _prim.push(i);
      }
    }
  }
  Console.WriteLine("Prime numbers:");
  for (var i = 0; i < _prim.length; i++) {
    Console.Write(_prim[i] + " ");
  }
  Console.WriteLine();
  Console.WriteLine("Found " + _prim.length + " prime numbers.");
  Console.WriteLine();
  return _prim;
}

// test some individual pre-calculated numbers

function CheckSome() {
  var num1 = prim[prim.length - 1];
  var num2 = num1 - 1;
  Console.WriteLine("Test: " + num1.toString() + ". Is it a prime number? " + Is_prime(num1));
  Console.WriteLine("Test: " + num2.toString() + ". Is it a prime number? " + Is_prime(num2));
}

function Is_prime(n) {
  if (n > MaxNum) throw "ERROR: n must be <" + MaxNum + "!";
  if (prim.indexOf(n) === -1)
    return false;
  else
    return true;
};


// ------------ HELPERS to display on screen ------------
var Console = {
  Section: 1,
  SectionId: "#section1",
  NewSection: function() {
    var $currentSection = $(this.SectionId);
    this.Section++;
    this.SectionId = "#section" + this.Section.toString();
    $currentSection.before('<div id="section' + this.Section.toString() + '"></div>');
  },
  Write: function(str) {
    $(this.SectionId).append(str);
  },
  WriteLine: function(str) {
    if (str !== undefined && str !== null && str !== "") this.Write(str);
    this.Write("<br/>");
  }
};


var GetMaxNum = function() {
  var result = $("#MaxNumSelect option:selected").val();
  return result;
}

$(document).ready(function() {
  $("#MaxNumSelect").change(function() {
    MaxNum = GetMaxNum();
    Console.NewSection();
    Main();
    Console.WriteLine("---------------------------------");
  });
  Main();
});

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div>Select max number:&nbsp;
  <select id="MaxNumSelect">
    <option value="10000" default="default">10000</option>
    <option value="100">100</option>
    <option value="1000">1000</option>
    <option value="100000">100000</option>
  </select>
</div>

<div id="results">
  <div id="section1"></div>
</div>

In the above example, we have tested the first 10000 natural numbers. To decide if a given number is a prime number, you simply check if it is contained in the array prim:

function Is_prime(n) {
    if (n>MaxNum) throw "ERROR: n must be <"+CalcToNum+"!";
    if (prim.indexOf(n)===-1)
      return false;
    else
      return true;
};

Of course, in order for this to work the prime numbers need to be pre-calculated.

Example: alert(Is_prime(25)); - returns false, because 25 is no prime number.

Note: The number range must be checked, because the function Is_prime can decide only for numbers which are previously tested by the sieve above. If the array is too small for the number to check (i.e. if not enough prime numbers are pre-calculated), an error is thrown.

Answer 9

function isPrime(number) {

  // Immediate exit cases
  switch(true){
    case (number < 2):
      return console.log("Please enter a number greater than or equal to 2.")
    case (number === 2 || number === 3):
      return console.log(number + " is a prime number!")
  }

  // Process number if it does not meet above requirements
  var num = Math.floor(Math.sqrt(number))

  for(var i = 2; i <= num; i++) {
    if(number % i === 0)
      return console.log(number + " is not a prime number")
    else
      return console.log(number + " is a prime number!")
  } 
}

isPrime(27) // 27 is a prime number!
isPrime(30) // 30 is not a prime number
isPrime(55) // 55 is a prime number!
isPrime(2)  // 2 is a prime number!

Answer 10

There is a function that will return true if the number is prime and false if it is not:

function isPrime(x){     
      d = x-1;
      while (d > 1){
        if ((x % d) == 0) return false;
        d--;
      }
      return true;
    }

Checkout the demo: http://jsbin.com/velapabedi/1/

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>JS Bin</title>
  
  <script>
    function isPrime(x){     
      d = x-1;
      while (d > 1){
        if ((x % d) == 0) return false;
        d--;
      }
      return true;       
      
    }
    
    
    if (isPrime(41)){
      alert('Prime');
    }
    else{
      alert('Not Prime');
    }
  </script>
</head>
<body>

</body>
</html>

Answer 11

Do you want to know how to determine a number is prime or composite. This code make you understand easily. Input from a number 2.

var p = prompt("Insert a number for check","");
var x = " is a prime number";
for(i=2; i<p; i++){
    if(p%i === 0){
        x = " is a composite number";
        break;
    }
}
alert(p+x);

Answer 12

You should return a bool value and new function can be:

function(n) {
    if(n === 1) { return false;}
    else if(n == 2) { return true;}
    else if(n == 3) { return true;}
    else { 
        for(i=Math.floor(Math.sqrt(n));i>=2;i--){
            //console.log(i);//maybe another var in here? 
                if(n%i ==0 || n%2 ==0 || n%3 == 0) {return false;} 
        } 
        }
    return true;
};

In the OP, the control if(n%i !==0 && n%2 !==0 && n%3 !== 0) {return n;} was problematic because even if only single i satisfies this condition, the function returns the number as prime.

Answer 13

In your if statement you got

if(n%i !==0 && n%2 !==0 && n%3 !== 0)

you for loop is going till i >= 2, so the n%2 !== 0 is useless, when i = 2, your if would look like:

if(n%2 !==0 && n%2 !==0 && n%3 !== 0)

Thats 2x the same check, the same is for n%3, its already checked :).

you should keep a bool to check the n%i !== 0, if it never reach this it's a prime.

Good luck with your homework :).