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 1 of 2 12 LastLast
Results 1 to 15 of 23
  1. #1
    New to the CF scene
    Join Date
    Jun 2013
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Finding prime numbers code issue

    I'm a beginner in JS and can't figure out why this isn't working right.

    It prints out "2,2,2,2,2,2,2" and so on, but I need it to print the first 100 prime numbers.

    Any help is appreciated.

    Code:
    var primeNumbers = []; //Prime numbers stored here
    
    while(primeNumbers.length <= 100){
    	
    	//Number to be tested if it is a prime.
    	var candidate = 2;
    
    	for(var i = 2; primeNumbers.length <= 100; i++)
    	{
    		if(candidate % i == 0){
    			continue;
    		}else{
    			i = 0;
    			primeNumbers.push(candidate);
    		}
    	};
    	
    	candidate++;
    };
    
    for(var print = 0; print <= primeNumbers.length; print++){ 
    	//Prints out the prime #'s stored in var primeNumbers.
    
    		console.log(primeNumbers[i] + ",");
    
    };

  • #2
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    Code:
    for(var print = 0; print <= primeNumbers.length; print++){ 
    	//Prints out the prime #'s stored in var primeNumbers.
    
    		console.log(primeNumbers[i] + ",");
    
    };
    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.

  • #3
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    But the algorithm you are using still won't work.

    It's horribly broken.
    Last edited by Old Pedant; 06-26-2013 at 02:36 AM.
    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
    New to the CF scene
    Join Date
    Jun 2013
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Thank you, i didn't catch that, but it is still printing 2 over and over.

    For a more efficient way to find primes, do you mean the Sieve of Eratosthenes?

  • #5
    New to the CF scene
    Join Date
    Jun 2013
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Reading this article http://en.wikipedia.org/wiki/Primali...#Naive_methods

    Changed it a bit, although still bad and broken..

    Code:
    var primeNumbers = []; //Prime numbers stored here
    
    while(primeNumbers.length <= 100){
    	
    	//Number to be tested if it is a prime.
    	var candidate = 2;
    
    	for(var i = 2; i <= Math.sqrt(candidate); i++)
    	{
    		if(candidate % i === 0){
    			continue;
    		}else{
    			primeNumbers.push(candidate);
    			i = 2;
    		}
    	};
    	
    	candidate++;
    };
    
    var output = primeNumbers.join(); //Combines array into string and prints it.
    console.log(output);

  • #6
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    The Sieve is the most efficient that I know of.

    But even one like yours can be improved two-fold by just considering odd numbers.
    Just push 2 into the array and then start with 3.
    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.

  • #7
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    But even better: Why try moduloing the candidate with *every* number (even every odd number)?? Why not just try testing it against ALL THE PRIMES LESS THAN itself!
    Code:
    <script type="text/javsascript">
    // Prime numbers stored here
    // ..start with 2 as only even prime
    var primeNumbers = [2]; 
    
    var candidate = 3;  // start with first odd number
    
    while ( primeNumbers.length < 100 )
    {
        var prime = true; // assume candidate is prime
    
        // no point in checking against primeNumbers[0],
        // which is 2.  Because our candidate value will 
        // never be even...so start at element 1 of the array instead
        for ( var i = 1; i < primeNumbers.length; ++i )
        {
    	if ( candidate % primeNumbers[i] == 0)
            {
                 prime = false;
                 break; // no point in continuint
            }
        }
        if ( prime ) primeNumbers.push(candidate);
        candidate += 2; // skip the even numbers
    };
    alert( primeNumbers );
    </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.

  • Users who have thanked Old Pedant for this post:

    Devin_p (06-26-2013)

  • #8
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    Even getting all the prime numbers less than 1000, the Sieve method is roughly 3 times faster than the method shown above. I would expect its advantage to grow as the number of prime numbers desired grows.

    EDIT: I couldn't stand it; had to test my gut feelings.

    Yes, if you ask for all prime numbers less than 5000, then the Sieve outperforms the modulo by a factor of *TEN*.

    Not surprising, but I just wanted to check my sanity.
    Last edited by Old Pedant; 06-26-2013 at 04:52 AM.
    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.

  • #9
    New to the CF scene
    Join Date
    Jun 2013
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Thank you for all your help and effort you put into this!

  • #10
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    Just for completeness, here's the version of the Seive of Erastothenes that I used:
    Code:
    <script type="text/javascript">
    var nums = [ ];
    var primes = [ ];
    var MAXNUM = 5000; // change this as desired
    for ( var n = 0; n < MAXNUM; ++n )
    {
        nums[n] = n;
    }
    // run the actual seive
    for ( var chk = 2; chk < MAXNUM; ++chk )
    {
        if ( nums[chk] != 0 )
        {
           primes.push(chk);
           for ( var mark = chk; mark < MAXNUM; mark+=chk )
           {
               nums[mark] = 0;
           }
        }
    }
    alert(primes);
    </script>
    There are ways to make that a little more efficient, but not enormously so.
    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.

  • #11
    Regular Coder
    Join Date
    Jan 2013
    Location
    Germany
    Posts
    578
    Thanks
    4
    Thanked 77 Times in 77 Posts
    Warning: Some math up ahead.

    Quote Originally Posted by Old Pedant View Post
    But even better: Why try moduloing the candidate with *every* number (even every odd number)?? Why not just try testing it against ALL THE PRIMES LESS THAN itself!
    Even better: Only try all integers less than or equal to the square root of the number [1][2] And now combining these two solutions, even better is to check all prime numbers less than or equal to the number [3].

    As for algorithms in general: First off, the Sieve of Eratosthenes could be improved, but one could also use another optimized version known as the Sieve of Atkin which is better by a factor of 1/(log log n).

    [1] If p was not prime, it could be factored into p = ab. Without loss of generality, assume a > sqrt(p). It would immediately follow that b < sqrt(p). Since finding only one factor suffices to disprove that p is a prime, it is enough to check all integers less than or equal to the square root of the number in question.

    [2] The number of primes <= x is asymptotically equivalent to x/ln(x). The limit of that divided by sqrt(x) is -- as one can see with fairly basic maths -- infinite, which means that it is by far better to use sqrt(x). As an additional benefit the test is independent of all prime numbers smaller than the number in question.

    [3] Again, if p was not prime, there would be a factorization p = ab. In [1] we have seen that we can assume a <= sqrt(p). Now, if a was not prime itself, it could be further factorized into a = xy. The same argument would show (without loss of generality) that x <= a <= sqrt(p).

  • #12
    Senior Coder
    Join Date
    Sep 2010
    Posts
    1,974
    Thanks
    15
    Thanked 229 Times in 229 Posts
    Quote Originally Posted by Old Pedant View Post
    But even better: Why try moduloing the candidate with *every* number (even every odd number)?? Why not just try testing it against ALL THE PRIMES LESS THAN itself!
    Actually, it only needs to be test against all primes less than the square root of itself, so you just need to make a list of them.
    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.

  • #13
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    Well, even the version of the Sieve of Erastothenes that I used is not the best, as I said. I know it can easily be made about 4 times as efficient. But that code is pretty simple and compact, and unless you are going for a huge number of primes it's more than adequate.
    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.

  • #14
    Regular Coder
    Join Date
    Jan 2013
    Location
    Germany
    Posts
    578
    Thanks
    4
    Thanked 77 Times in 77 Posts
    @DrDos
    Less than or equal to(!) -- this is crucial, otherwise you would count every square of a prime number as prime.

    @OldPedant

    I agree that there is no need to improve it if it satisfies your needs. But switching to the square root is not a factor of four, we're talking orders of magnitude and a legit asymptotic benefit here. It's not a very special improvement either, it's fairly common to write even simple implementations using the square root as the bound. So yes, for the first few hundred primes it should be practically irrelevant, but I believe that with technical algorithms like this, at least showing what impact little details can have is important.

  • #15
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,441
    Thanks
    76
    Thanked 4,372 Times in 4,337 Posts
    Okay, I give up. How does using the square root of the number being checked apply to the Sieve of Erastothenes algorithm???

    Look at my code in post #19.

    To do the prime.push(chk), we must loop all the way to the max num we are wanting to check.

    And then the inner loop must also go all the way to that same max num to be sure all the multiples of the given prime are marked.

    But notice that the marking loop at least only starts at the found prime number, so it's not terrible. But we could get 4 times as efficient by only considering odd numbers and by not bother with marking even multiples of a prime number. Oh, and we don't need to mark the prime number we just found.

    Further than that...I dunno. What do you think can be done? And how does square root apply to this algorithm??
    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.


  •  
    Page 1 of 2 12 LastLast

    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
    •