Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 7 of 7
  1. #1
    New to the CF scene
    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

  • #2
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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 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.

  • #3
    Regular Coder
    Join Date
    Mar 2006
    Posts
    726
    Thanks
    35
    Thanked 132 Times in 123 Posts
    Here is a way to get the primes-


    Code:
    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(', '))

  • #4
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    Sort of defeats the point of a homework assignment...

  • #5
    Regular Coder
    Join Date
    Mar 2006
    Posts
    726
    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; 01-28-2009 at 12:38 AM.

  • #6
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    17,918
    Thanks
    203
    Thanked 2,531 Times in 2,509 Posts
    A small correction:-

    Quote Originally Posted by mrhoo View Post
    Here is a way to get the primes-


    Code:
    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 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 = num-2;
    nopar = -1;
    cntt = 2;
    Last edited by Philip M; 01-28-2009 at 08:55 AM.

  • Users who have thanked Philip M for this post:

    mrhoo (01-28-2009)

  • #7
    Regular Coder
    Join Date
    Mar 2006
    Posts
    726
    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; 01-28-2009 at 02:52 PM.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •