
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 nonprimes as primes.
I can't figure out what the problem is, can anyone help me?
Appel

You have to test all primes[n] value while primes[n]*primes[n]<=x before to increment x !

Originally Posted by 007Julien
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 squareroot 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; 06242011 at 07:04 AM.

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 httpequiv="contenttype" content="text/html; charset=iso88591">
<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>

Originally Posted by 007Julien
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

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...

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) !

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

Forum Rules

