View Full Version : First 1000 primes

twitch827

01-27-2009, 11:55 PM

im taking a javascript class and i need a script that displays the first 1000 prime numbers in a table with 10 numbers per row. ive been trying on my own for about 4 hours now and am really confused. i just started the class and have only started learning javascript 3 days ago. im lost. if it would help you to help me i can post what im sure is my atrocious code. thanks for any help

Well, the best way to figure out primality for a large group of numbers is called the Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

The issue is, after running, given a list from 1 to n, you can determine which numbers in that list are prime. It doesn't tell you how large n should be in order to get 1000 prime numbers.

Fortunately, we know that that the density of prime numbers roughly follows n/log(n) (e.g. the number of prime numbers less than n is asymptotically n/log(n)). You can plug n/log(n)-1000 = 0 into a computer or calculator and see that n approximately equals 9118. Let's just assume an upper bound of 9409 to be sure (the choice may seem random, but it is the least perfect square greater than 9118).

Now, you have to implement the sieve from a list with 9409 elements. Doing that for you would be doing your homework, but the wikipedia article gives some straight-forward directions in doing it.

There are other, slower ways of doing the same thing. For example, create a list from 1 to 9409. For each number in the list, check its primality. The thing is, now you're running a primality test 9409 times, which will be very slow.

Good luck.

mrhoo

01-28-2009, 12:56 AM

Here is a way to get the primes-

Math.getPrimes=function(max, min){

min= min || 2;

var notP= [1, 1];

var pA= [], i, j;

var limit= Math.sqrt(max)+1;

for(j= 3; j<= limit; j= j+2){

if(!notP[j]){

for(i= j+j; i<= n; i= i+j) notP[i]= 1;

}

}

i= min;

while(i++< max){

if(!notP[i] && i%2) pA.push(i);

}

if(min<= 2) pA.unshift(2);

return pA;

}

//test

var Primes=Math.getPrimes(1000);

alert(Primes.join(', '))

Sort of defeats the point of a homework assignment...

mrhoo

01-28-2009, 01:35 AM

I disagree with jkd, but not usually.

After all, Eratosthenes told me how to do it.

I nearly always go a little out of the way when a new member asks his very first question.

There is a lot still to do, if he is to use javascript to build a table of the primes.

Philip M

01-28-2009, 09:02 AM

A small correction:-

Here is a way to get the primes-

Math.getPrimes=function(max, min){

min= min || 2;

var notP= [1, 1];

var pA= [], i, j;

var limit= Math.sqrt(max)+1;

for(j= 3; j<= limit; j= j+2){

if(!notP[j]){

for(i= j+j; i<= max; i= i+j) notP[i]= 1;

}

}

i= min;

while(i++< max){

if(!notP[i] && i%2) pA.push(i);

}

if(min<= 2) pA.unshift(2);

return pA;

}

//test

var Primes=Math.getPrimes(1000);

alert(Primes.join(', '))

mrhoo's script generates the prime numbers below 1000, not the first 1000 prime numbers (although I expect that is what the OP really requires - or does he mean 100?).

This seems a very difficult assignment to set for someone who only started learning Javascript 3 days ago. There is a script at http://www.codingforums.com/showthread.php?t=104075 which the OP might be able to understand better. That does (or might) generate the first 1000 primes, although it may well choke the computer on such a large number.

In case anyone wishes to use this script, it also has a couple of imperfections, and should be revised as follows:-

function numberprimes(num) {

noptr = num-2;

nopar = -1;

cntt = 2;

mrhoo

01-28-2009, 03:46 PM

Right you are, Philip.

var A=Math.getPrimes(7919);

(I got the 1000th prime by reading A[999] of X=Math.getPrimes(10000))

Powered by vBulletin® Version 4.2.2 Copyright © 2015 vBulletin Solutions, Inc. All rights reserved.