Enjoy an ad free experience by logging in. Not a member yet? Register.


Results 1 to 7 of 7
Thread: First 1000 primes

01272009, 10:55 PM #1
 Join Date
 Jan 2009
 Posts
 1
 Thanks
 0
 Thanked 0 Times in 0 Posts
First 1000 primes
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
01272009, 11:21 PM
#2
Well, the best way to figure out primality for a large group of numbers is called the 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 straightforward 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.
01272009, 11:56 PM
#3
 Join Date
 Mar 2006
 Posts
 725
 Thanks
 35
 Thanked 132 Times in 123 Posts
Here is a way to get the primes
//testCode: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; }
var Primes=Math.getPrimes(1000);
alert(Primes.join(', '))
01282009, 12:23 AM
#4
Sort of defeats the point of a homework assignment...
01282009, 12:35 AM
#5
 Join Date
 Mar 2006
 Posts
 725
 Thanks
 35
 Thanked 132 Times in 123 Posts
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.
Last edited by mrhoo; 01282009 at 12:38 AM.
01282009, 08:02 AM
#6
 Join Date
 Jun 2002
 Location
 London, England
 Posts
 17,730
 Thanks
 202
 Thanked 2,508 Times in 2,486 Posts
A small correction:
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 Prime numbers 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 = num2;
nopar = 1;
cntt = 2;
Last edited by Philip M; 01282009 at 08:55 AM.
Users who have thanked Philip M for this post:
mrhoo (01282009)
01282009, 02:46 PM
#7
 Join Date
 Mar 2006
 Posts
 725
 Thanks
 35
 Thanked 132 Times in 123 Posts
Right you are, Philip.
var A=Math.getPrimes(7919);
(I got the 1000th prime by reading A[999] of X=Math.getPrimes(10000))
Last edited by mrhoo; 01282009 at 02:52 PM.