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.
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 square-root x, round it up, and store that value to check primes[n] against.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 .
Great wit and madness are near allied, and fine a line their bounds divide.
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>
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?
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).
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!
Thread Information
Users Browsing this Thread
There are currently 1 users browsing this thread. (0 members and 1 guests)
Tags for this Thread
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
Forum Rules
Reply With Quote
Originally Posted by 007Julien
Bookmarks