Need to generate prime numbers in JavaScript

Question

I am writing a JavaScript to generate prime numbers from 2 to 100. However It doesn't work and can't figure it out.

will you help me please?

var array = new Array(100);

for (var i=2 ; i<=array.length-1; i++) {
    if((i%2===0) || (i%3===0))
        continue;
    document.writeln(i+",");
}

I modified my answer, but now it doesn't print 2 & 3; how can I include 2 & 3... result is :

5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97

Solution 1

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

function display(n) {
    var arr = [2];
    for ( var i = 3; i < n; i+=2 ) {
        if ( isPrime(i) ) {
            arr.push(i);
        }
    }
    console.log(arr); // use arr result on your own
}

display(100);

NOTE: Specify n parameter in display function and get the primes from 2 to n ...

Check out JSFiddle

Updateing: Note that the above script is correct and I'm leaving it, though adding the same function with one functionality in addition:

function prime(n,flag) {
    ( typeof flag === "undefined" || flag === false ) ? flag = false : flag = true;

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

    if ( flag ) {
        var arr = [2];
        for ( var i = 3; i <= n; i+=2 ) {
            if ( isPrime(i) ) {
                arr.push(i);
            }
        }
        return arr;
    } else {
        return isPrime(n);
    }
}

Explanation: prime function expect two parameters, first one is required and the second is optional. If only first parameter is specified function will return true or false based on number belongs or not to primes. If second parameter is specified as true (or any other type except undefined and false) function will return array of primes from 2 to n. For example:

console.log(prime(2)); // returns true ( 2 is prime )
console.log(prime(8)); // returns false ( 8 isn't prime )

console.log(prime(100,true)); // returns [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]

Solution 2

var enterNumber = prompt("Enter number: ");

for(var i=2; i<=enterNumber ;i++){

        var isPrime = true;

        for(var j=2; j<i; j++){
            if(i%j === 0 && i !== j){
                isPrime = false;
            }
        }
        if(isPrime === true){
            console.log(i);
        }
    }

Solution 3

A version using javascript generators:

function* take(length, iterable) {
  for (let x of iterable) {
    if (length <= 0) return;
    length--;
    yield x;
  }
}

function* primes() {
  let n = 2;

  while (true) {
    if (isPrime(n)) yield n;
    n++;
  }

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

console.log([...take(4, primes())]); //[ 2, 3, 5, 7 ]

Solution 4

Your original code has numerous flaws. To implement the Sieve of Eratosthenes, you need to add each prime you find to an array, and then test the next candidate prime against every prime you've found so far. If the candidate is not divisible by any of the primes in the array, then it's prime, and you can add it to your array of primes.

Here's a working version (Demonstration):

function start() {    
    var array = [2, 3];
    for (var i = 5; i <= 100; i += 2) {
        if (array.every(function(p) { return i % p; })) {
            array.push(i);
        }
    }
    var result = array.join(",");
    document.getElementById("output").innerHTML = result;
}
start();

Note that this depends on Array.prototype.every which was introduced in ECMAScript 5.

Solution 5

You have a lot of ways to achieve this.

You were basically on the right way, however, you have to check every number if it's divisible by every prime you determined so far:

var primes = [2],isPrime;

for (var i=3;i<100;i+=2){
    isPrime = true;
    // test the number you are examaning against
    // all the primes you found so far
    for (var j = 0;j<primes.length;j++){
        if (i%primes[j]==0){
            isPrime=false;
            break;
        }
    }
    if(isPrime){primes.push(i)}
}
console.log(primes);

See the result here

Or you can use the Sieve of Eratosthenes which sorts out all numbers to avoid duplicated tests.

A true implementation of the SoE:

// initialize the array first
var numbers = [], primes = [], maxNumber = 100;

for(var i = 2;i<=maxNumber;i++){
 numbers.push(i);   
}

while(numbers.length){
    primes.push(numbers.shift());
    numbers = numbers.filter(
        function(i){return i%primes[primes.length-1]!=0}
    );
}

console.log(primes);

Demo

View more solutions

Comments

[Christoph]

Strictly spoken this is not the SoE. You test each number multiple times, which is against the purpose of SoE. Look at the second solution of my answer, which is a SoE.

[Christoph]

Your solution is rather inefficient. The display loop better started from 3 and incremented by 2 and isPrime only needs to divide by prime numbers.

[nanobash]

@Christoph I've tested elapsed time between discussed solution algorithms and difference occurs sensible about 100 milliseconds when N is 100000

[None]

You only need to check up to the square root of num.

[Kristina Bressler]

I'm trying to understand how the function isPrime(num) works. What I can understand is that the function display(n) produce this array [2,3,5,7,9] and so on with odd numbers. Next, this array is filtered through function isPrime(num). Starting with var i = 2; i < num; i++ and using this equation num % i === 0, it should go like this, 3(num) % 2(i) has remainder, 5(num) % 3(i) has remainder, 7(num) % 4(i) has remainder, but the next one, 9(num) % 5(i) also have remainder but 9 isn't a prime number. What is supposed to happen?

[nanobash]

@KristinaBressler if you specify n number as an argument without flag, flag considered to be a false and function returns whether specified integer is prime number or not. On the other hand if flag set to true, function returns prime numbers up to specified n integer. Inside isPrime function determines whether number is prime or not by checking the reminder, whether number can be divided to any number up to specified n number, and returns boolean based on it. and Yes 9 is not a prime nuber. function returns false if you try.

[Kristina Bressler]

Umm...I'm asking about the first solution, not the second updated solution that you posted. I wanted to know if the output is correct for this condition num % i === 0: 3(num) % 2(i), 5(num) % 3(i), 7(num) % 4(i), 9(num) % 5(i), 11(num) % 6(i), and so on...

[nanobash]

@KristinaBressler Yes it is correct if we don't consider passing in isPrime function 0, 1 and 3 values. In order to work for those values add if clause from updated version.

[Ganesh Karewad]

please add some explanation to your answer. It will help others to understand it better.