# Thread: problems with prime numbers

1. Registered User
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>
<title>Problem 7 project euler</title>
<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. Registered User
Join Date
Oct 2010
Location
Versailles, France
Posts
1,290
You have to test all primes[n] value while primes[n]*primes[n]<=x before to increment x !

3. Registered User+
Join Date
Aug 2007
Posts
3,767
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 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 06:04 AM.

4. Registered User
Join Date
Oct 2010
Location
Versailles, France
Posts
1,290
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">
<meta http-equiv="content-type" content="text/html; charset=iso-8859-1">
<title>Prems</title>
<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. Registered User
Join Date
Jun 2011
Posts
5
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?

6. Registered User
Join Date
Oct 2010
Location
Versailles, France
Posts
1,290
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. Registered User
Join Date
Oct 2010
Location
Versailles, France
Posts
1,290
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. Registered User
Join Date
Jun 2011
Posts
5
ah, now I get it!

it's working, thank you very much!