Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 2 of 2 FirstFirst 12
Results 16 to 23 of 23
  1. #16
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,028
    Thanks
    75
    Thanked 4,325 Times in 4,291 Posts
    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 non-null would do
           }
        }
    }
    alert(primes);
    </script>
    Improvements:
    (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.

  2. #17
    Senior Coder
    Join Date
    Sep 2010
    Posts
    1,903
    Thanks
    15
    Thanked 226 Times in 226 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.

  3. #18
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,028
    Thanks
    75
    Thanked 4,325 Times in 4,291 Posts
    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 non-marked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all non-primes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the non-marked 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.

  4. #19
    Senior Coder
    Join Date
    Sep 2010
    Posts
    1,903
    Thanks
    15
    Thanked 226 Times in 226 Posts
    Quote Originally Posted by Old Pedant View Post
    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 non-marked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all non-primes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the non-marked numbers so won't find all the primes.
    You're right sir! I really meant the primes in the first million numbers, not the first million primes.
    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.

  5. #20
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,028
    Thanks
    75
    Thanked 4,325 Times in 4,291 Posts
    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 non-null would do
           }
        }
    }
    for ( var chk = 3; chk < MAXNUM; chk += 2 )
    {
        if ( nums[chk] == null ) primes.push(chk);
    }
    alert(primes);
    </script>
    All that really saves is the time for the inner for loop to discover that it won't run at all once chk is past the square root of max. At the expense of having to run another loop to collect the primes. I'd guess that's close to a wash.
    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.

  6. #21
    Regular Coder
    Join Date
    Jan 2013
    Location
    Germany
    Posts
    578
    Thanks
    4
    Thanked 77 Times in 77 Posts
    Quote Originally Posted by Old Pedant View Post
    Okay, I give up. How does using the square root of the number being checked apply to the Sieve of Erastothenes algorithm???
    Yeah, you're right – I mixed some things up there (namely the sieve and a prime number check). My mistake.

  7. #22
    Regular Coder
    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>
    After 9 you have only to check 5+6*k and 5+6*k+2 (the other are even or divisible by 3)
    Strange prime numbers : 11113, 11117, 11119, 22229, 33331, 44449, 77773, 88883, 99991 ...
    Last edited by 007julien; 06-28-2013 at 10:36 PM.

  8. #23
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    17,898
    Thanks
    203
    Thanked 2,530 Times in 2,508 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.


 
Page 2 of 2 FirstFirst 12

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
  •