Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 16 to 23 of 23
Thread: Finding prime numbers code issue

06272013, 06:48 PM #16
Here's (nearly) the best I can do with the Sieve of Erastothenes:
Code:<script type="text/javascript"> var nums = [ ]; var primes = [2]; var MAXNUM = 500; // change this as desired // run the actual seive for ( var chk = 3; chk < MAXNUM; chk += 2 ) { if ( nums[chk] == null ) { primes.push(chk); for ( var mark = chk*3; mark < MAXNUM; mark += chk*2 ) { nums[mark] = 0; // any nonnull would do } } } alert(primes); </script>
(a) no need to initialize the array
(b) only checks odd numbers
(c) only marks odd increments of a found prime
(d) doesn't bother marking a found prime
The next step: Would only save memory, not speed. And probably not even that with JavaScript coding. Have each element of the array represent an ODD number. That is, the element numbering doesn't match the numbers represented. So the array can be half the size it is now.
Aside from changing algorithms, do you see a way to improve that?An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.

06272013, 06:50 PM #17
 Join Date
 Sep 2010
 Posts
 1,912
 Thanks
 15
 Thanked 227 Times in 227 Posts
Let's say that you want to check the first million primes, notice that I've conveniently chosen a limit that is the square of another number, and that number is composite ! Then you only need to check against primes that are less than 1,000. Make your life simpler by setting reasonable conditions.
Welcome to http://www.myphotowizard.net
where you can edit images, make a photo calendar, add text to images, and do much more.
When you know what you're doing it's called Engineering, when you don't know, it's called Research and Development. And you can always charge more for Research and Development.

06272013, 07:00 PM #18
DrDos: Ummm...no.
(a) The first million *PRIMES* will not be found in the first million numbers. Not even close. I think you mean "all prime numbers that are less than one million".
(b) If that's a comment on my Sieve of Erastothenes implementation, I still don't see it. With the Sieve, any nonmarked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all nonprimes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the nonmarked numbers so won't find all the primes.An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.

06272013, 07:03 PM #19
 Join Date
 Sep 2010
 Posts
 1,912
 Thanks
 15
 Thanked 227 Times in 227 Posts
Welcome to http://www.myphotowizard.net
where you can edit images, make a photo calendar, add text to images, and do much more.
When you know what you're doing it's called Engineering, when you don't know, it's called Research and Development. And you can always charge more for Research and Development.

06272013, 07:06 PM #20
Okay, I do see that the marking and checking can be done separately, and then the marking only has to go to the square root of the max:
Code:<script type="text/javascript"> var nums = [ ]; var primes = [2]; var MAXNUM = 500; // change this as desired // run the actual seive for ( var chk = 3; chk < Math.sqrt(MAXNUM); chk += 2 ) { if ( nums[chk] == null ) { for ( var mark = chk*3; mark < MAXNUM; mark += chk*2 ) { nums[mark] = 0; // any nonnull would do } } } for ( var chk = 3; chk < MAXNUM; chk += 2 ) { if ( nums[chk] == null ) primes.push(chk); } alert(primes); </script>
An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.

06272013, 07:45 PM #21
 Join Date
 Jan 2013
 Location
 Germany
 Posts
 578
 Thanks
 4
 Thanked 77 Times in 77 Posts

06282013, 05:52 PM #22
 Join Date
 May 2012
 Location
 France
 Posts
 224
 Thanks
 0
 Thanked 32 Times in 30 Posts
A simple page for prime numbers which use the preceding primes to test a new number.
And a more subtle function (from rnd.me ? I can not find the post) that stores the previous calculations to go faster
Code:<script type="text/javascript"> (function(){ function isPrime(){ var n=this; if(isPrime[n]) return true; if( n<11 ! ((n%2)&&(n%3)&&(n%7)&&(n%9)) ) return false; for (var i=5, l=Math.sqrt(n)+1; i<l; i+=6){ if( !(n%i)  !(n%(i+2)) ) return false; } return isPrime.n++ < 1e6 ? (isPrime[n]=true) : true; }; var p=isPrime;p.n=0;p[2]=p[3]=p[5]=p[7]=true; Number.prototype.isPrime=p; }()); // Use var nmb=33353; alert(nmb.isPrime()) // true </script>
Strange prime numbers : 11113, 11117, 11119, 22229, 33331, 44449, 77773, 88883, 99991 ...Last edited by 007julien; 06282013 at 10:36 PM.

06282013, 05:59 PM #23
 Join Date
 Jun 2002
 Location
 London, England
 Posts
 17,910
 Thanks
 203
 Thanked 2,531 Times in 2,509 Posts
Code:Is this number prime? <input type = "text" id = "pn" onblur = "return alert(Number.prototype.isPrime(this.value))"> <script type = "text/javascript"> Number.prototype.isPrime = function (which) { var num = Number(which), counter; if (num === 2) { return true; } if (num < 2  (num / 2) === Math.floor(num / 2)  num !== Math.floor(num)) { return false; } else { for (counter = 3; counter <= Math.sqrt(num); counter += 2) { if (num % counter === 0) { return false; } } return true; } } </script>
All the code given in this post has been tested and is intended to address the question asked.
Unless stated otherwise it is not just a demonstration.