12
\$\begingroup\$

I had to look up some other solutions online because I could not figure it out on my own. I really wish I could have come up with it completely on my own, but that didn't happen. Nevertheless, please review my prime number program and let me know if there are any improvements I should make or advice your would like to give me about it.

     var primes = [];                    // will become a list of prime numbers

primes_loop:
for (var n = 2; n < 10; n++) {

    if (n === 2) {
        primes.push(n);              // first prime number is stored
        continue primes_loop;        // continue iteration of the loop
    }

    divisors_loop:
    for (var i = 2; i < n; i++) {

        if (n % i === 0) {
            break divisors_loop;     // n is not prime if condition is true
        }
        else {
            primes.push(n);          // update prime list with the prime number
        }

    }

}

for (var index = 0; index < primes.length; index++) {
    console.log(primes[index]);
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Trial division, nice first step! Now try the Sieve of Eratosthenes. Too intuitive? Try the Sieve of Atkin! Upgrade that algorithm for better time & space performance! \$\endgroup\$ Mar 27, 2014 at 3:59
  • \$\begingroup\$ for (var i = 2; i < n; i++) I am kind of against using this kind of a loop, the number of iterations can be reduced by half just by changing it to, for (var i = 2; i < n/2; i++) Furthermore, if we are testing a very large number to be prime or not, using i=2 ; i< sqrt(n) ; i++ reduces the number of iterations exponentially. (the last code snippet was a C code, not sure about the sqrt() function in javascript) \$\endgroup\$
    – debal
    Mar 27, 2014 at 4:03
  • \$\begingroup\$ n is the number that is being tested for being prime or not, while the loop condition that is mentioned is for testing if a number is prime or not. Lets consider n=11, then the loop runs from i=2; i<5, no divisors found and hence prime. for a number n, the number of factors from [1,n/2] is equal top the number of factors from [n/2,n] hence the second part of the iteration is a repeat of the first part. I will try and fetch the algo that proves it. \$\endgroup\$
    – debal
    Mar 27, 2014 at 4:10
  • \$\begingroup\$ If I am reading the code right then i see two major loops, for (var n = 2; n < 10; n++) for generating the range of numbers from which he will print the ones that are prime, and for (var i = 2; i < n; i++) that tests if the generated number is prime or not. The value of n that is being generated in the first loop is being used as the upper limit for the second loop that tests if the number is primie or not. This is the loop that I am referring to. \$\endgroup\$
    – debal
    Mar 27, 2014 at 4:16
  • 1
    \$\begingroup\$ I you right, I though he was using the partial array of primes to check for primality of the larger number. He only needs to check [2, floor(sqrt(n))] to determine primality of n. \$\endgroup\$ Mar 27, 2014 at 4:20

2 Answers 2

6
\$\begingroup\$

First of all, there's a slight problem with your code. I get this output:

2, 3, 5, 5, 5, 7, 7, 7, 7, 7, 9

So it repeats quite a bit, and -- wait, 9 is not a prime number. Oops.

For, say, numbers up to 25, you'd get 21 instances of 23 in your array. And we'd get a 24 too, although that's not prime. We'll deal with that in a second.

The way your code runs, you don't need the labels (primes_loop and divisors_loop); when you continue or break you do so for the "closest" loop you're in. So simply writing continue with no label will skip to the next iteration of the outer (prime) loop, and break will break the inner (divisor) loop.

However, a label might be handy for a revised version that actually does find primes and only primes (of course, there are other, smarter approaches to all of this, but I'm just sticking to the code that was posted):

var primes = [],
    limit = 10,
    n, divisor;

outerLoop: for( n = 2 ; n <= limit ; n++ ) {
  for( divisor = 2 ; divisor < n ; divisor++ ) {
    if( n % divisor === 0 ) {                     
      continue outerLoop; // not a prime, try the next n
    }
  }
  primes.push(n); // if we made it all the way here, then n is prime
}

After that, you'll be left with a primes array that looks like this:

[ 2, 3, 5, 7 ]

No repetition, and no false positives.

Of course, it'd be nicer to wrap as a function:

function findPrimes(limit) {
  var primes = [], n, divisor;

  outerLoop: for( n = 2 ; n <= limit ; n++ ) {
    for( divisor = 2 ; divisor < n ; divisor++ ) {
      if( n % divisor === 0 ) {
        continue outerLoop;
      }
    }
    primes.push(n);
  }

  return primes;
}
\$\endgroup\$
5
\$\begingroup\$

First, let's correct your algorithm (using this very similar code) and reformat just a little bit your code (with Fiddle's TidyUp):

JSFIDDLE

 var primes = []; // will become a list of prime numbers

 primes_loop: for (var n = 2; n < 10; n++) {

     if (n === 2) {
         primes.push(n); // first prime number is stored
         continue primes_loop; // continue iteration of the loop
     }

     divisors_loop: for (var i = 2; i < n; i++) {

         if (n % i === 0) {
             break divisors_loop; // n is not prime if condition is true
         }

     }

     if (n === i) {
         primes.push(n); // update prime list with the prime number
     }

 }

 for (var index = 0; index < primes.length; index++) {
     console.log(primes[index]);
 }

It printed repeatedly numbers because of the condition for primes.push, and it needed another condition, outside of the loop, to be correct (as it was, it only found odd numbers).

Next up, we don't really need tags for the inner loop. It's clear and very reasonable to remove it, and we even save the condition we just added:

 var primes = []; // will become a list of prime numbers

 primes_loop: for (var n = 2; n < 10; n++) {

     if (n === 2) {
         primes.push(n); // first prime number is stored
         continue; // continue iteration of the loop
     }

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

         if (n % i === 0) {
             break primes_loop; // n is not prime if condition is true
         }

     }

     primes.push(n); // update prime list with the prime number

 }

 for (var index = 0; index < primes.length; index++) {
     console.log(primes[index]);
 }

But, we might be able to wrap it up in a function and make it work faster, by skipping all multiples of 2:

JSFIDDLE

function findPrimes(lowerLimit, upperLimit) {

    var primes = []; // will become a list of prime numbers

    if (lowerLimit === 2) {
        primes.push(2);
    }

    if (lowerLimit % 2 === 0) {
        lowerLimit++;
    }

    primes_loop: for (var n = lowerLimit; n < upperLimit; n = n + 2) {

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

            if (n % i === 0) {
                break primes_loop; // n is not prime if condtion is ture
            }

        }

        primes.push(n); // update prime list with the prime number

    }

    for (var index = 0; index < primes.length; index++) {
        alert(primes[index]);
    }

}

findPrimes(2, 10);

This may get you started, but if primes is what you want, there are better methods (indeed, even this method may be optimized further).

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.