www.webdeveloper.com
Results 1 to 8 of 8

Thread: problems with prime numbers

  1. #1
    Join Date
    Jun 2011
    Posts
    5

    problems with prime numbers

    So I wrote this piece of code, which should display the first 10,001 prime numbers.

    Code:
    <html>
    <head>
    	<title>Problem 7 project euler</title>
    </head>
    <body>
    	<script>
    	var x = 3;
    	var primes = new Array();
    	primes[1] = 2;
    	var n = 1;
    	document.write("PRIME#1= 2" + "<br />")
    	while (n < 10001)
    		{
    		if (x%primes[n] == 0)
    			{
    			x = x + 2;
    			}
    		else if ((n + 1) < (primes.length))
    			{
    			n = n + 1
    			}
    		else
    			{
    			primes[(n+1)] = x;
    			document.write("PRIME#" + (n + 1) + "= " + primes[(n+1)] + "<br />");
    			x = x + 2;
    			n = 1
    			}
    		}
    	</script>
    </body>
    </html>
    now the problem is that somehow this code also interprets some non-primes as primes.

    I can't figure out what the problem is, can anyone help me?

    Appel

  2. #2
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,270
    You have to test all primes[n] value while primes[n]*primes[n]<=x before to increment x !

  3. #3
    Join Date
    Aug 2007
    Posts
    3,767
    Quote Originally Posted by 007Julien View Post
    You have to test all primes[n] value while primes[n]*primes[n]<=x before to increment x !
    Since speed will be an issue here, it's more efficient to square-root x, round it up, and store that value to check primes[n] against.

    There's some interesting posts here on prime numbers, isPrime for example. Generating primes is more efficient that checking them generally, because you only have to check divisibility by the previous primes rather than 6n+-1 or something like that.
    Last edited by Declan1991; 06-24-2011 at 07:04 AM.

  4. #4
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,270
    An object is more efficient to give prime numbers (it would be better to write the results less often)...

    HTML Code:
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
    <html><head>
      <meta http-equiv="content-type" content="text/html; charset=iso-8859-1">
      <title>Prems</title>
    </head><body>
      <div id="pge"></div>
    <script type="text/javascript">
    var Prm={
    	nbr:null,prm:[2],rng:1,
    	ini:function(){Prm.nbr=3;Prm.prm[Prm.rng++]=3;
    		document.getElementById('pge').innerHTML+=2, 3;
    		Prm.svr();
    	},
    	svr:function(){
    	 	Prm.nbr+=2; 
    		if (Prm.tst()) {document.getElementById('pge').innerHTML+=', '+Prm.nbr;
    			 Prm.prm[Prm.rng++]=Prm.nbr;}
    	 	setTimeout(Prm.svr,7);
    	},
    	tst:function(){var i=0,m=~~Math.sqrt(Prm.nbr);
    		while(Prm.prm[i]<=m && (Prm.nbr%Prm.prm[i])!=0) i++;
    		return (Prm.nbr%Prm.prm[i])!=0;}
    }
    Prm.ini();
    </script> 
    </body></html>

  5. #5
    Join Date
    Jun 2011
    Posts
    5
    Quote Originally Posted by 007Julien View Post
    You have to test all primes[n] value while primes[n]*primes[n]<=x before to increment x !
    I understand what you mean, but I thought that is already implented in my script?

    the last example you posted is far too complicated for me, I just started learning javascript.

    could you make an example with the change you suggested above already implented?

    thanks in advance

  6. #6
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,270
    Your code is quite good. You have only to made an n=1, if x is not prime, to obtain a good list of prime number...

    HTML Code:
    if (x%primes[n] == 0)
    		{
    			x = x + 2;
    			// New line
    			n=1;
    		}
    After you havn't to test all the primes. You can stop the loop when primes[n+1] is greater than Math.sqrt(x).

    Finally document.write is only gulty during the opening of the page...

  7. #7
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,270
    Sorry, You can stop the loop when primes[r+1] is greater than Math.sqrt(x). But r (the range of the prime numbers to test) is now not n (the range of the last prime number) !

  8. #8
    Join Date
    Jun 2011
    Posts
    5
    ah, now I get it!

    it's working, thank you very much!

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

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



Recent Articles