StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You're doing a lot in one function. The code may be a bit easier to follow if you break it up into two functions, one to make the list of primes and another to test if a specific number is prime:</p> <pre><code>function listPrimes( nPrimes ) { var primes = []; for( var n = 2; nPrimes > 0; n++ ) { if( isPrime(n) ) { primes.push( n ); --nPrimes; } } return primes; } function isPrime( n ) { var max = Math.sqrt(n); for( var i = 2; i <= max; i++ ) { if( n % i === 0 ) return false; } return true; } </code></pre> <p>Now you can run it in Node:</p> <pre><code>var fs = require('fs'); fs.writeFileSync( 'test.txt', listPrimes(100) ); </code></pre> <p>or directly in the browser console:</p> <pre><code>listPrimes( 100 ); </code></pre> <p>(I didn't test the code in Node, only in the browser.)</p> <p>A couple of related notes:</p> <ol> <li>The <code>sqrt()</code> calculation is moved outside the loop in <code>isPrime()</code>, so it doesn't have to be recalculated for each number you're testing.</li> <li>The <code>nPrimes</code> variable lets you generate the exact number of primes you want without the <code>542</code> hack.</li> </ol> <p>Having written this simple version, it's interesting to look at possible optimizations. One is to check for divisibility only on the previously generated primes, instead of checking all integers up to the square root. You could do that like this:</p> <pre><code>function listPrimes( nPrimes ) { var primes = []; for( var n = 2; nPrimes > 0; n++ ) { if( isPrime( n, primes ) ) { primes.push( n ); --nPrimes; } } return primes; } function isPrime( n, primes ) { var max = Math.sqrt(n); for( var i = 0; i < primes.length && primes[i] <= max; i++ ) { if( n % primes[i] === 0 ) return false; } return true; } </code></pre> <p>That may be faster if you're generating a large number of primes, although for 100 of them it hardly matters and I'd be inclined to stick with the simpler code.</p> <p>Of course if you're talking about optimization, it's always worth considering a different algorithm. The <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">Sieve of Eratosthenes</a> is a fun one because it's fast and fairly simple and easy to understand. That Wikipedia article has a great illustration of how it works. In JavaScript it might look something like this:</p> <pre><code>function listPrimes( max ) { // Start with an empty list of primes var primes = []; // Initialize the sieve - each number is prime unless proven otherwise var sieve = new Array( max ); for( var i = 1; i <= max; i++ ) { sieve[i] = true; } // Now check each number from 2 through max for( var p = 2; p <= max; p++ ) { if( sieve[p] ) { // p is prime, save it in the output list primes.push( p ); // Mark p * 2, p * 3, p * 4, etc. as non-prime for( var t = p * 2; t <= max; t += p ) { sieve[t] = false; } } } return primes; } </code></pre> <p>Yes, after recommending splitting the code into two functions, I'm now back to one function. :-)</p> <p>One difference about the Sieve is that you can't really say, "please give me the first N primes"; instead you ask it, "please give me all the primes less than N". But if N is a large number, it is much faster than the other approach. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload