Today's Question:  What are you most afraid of as a programmer?        GIVE A SHOUT

Technical Article => Programming =>  Algorithm

Generate first N prime numbers

  sonic0002      2013-06-29 22:08:22      6,948    5    7

Recently I am taking an online course named "Startup Engineering" on coursera. There is one assignment which is to use NodeJS to write a program to generate the first 100 prime numbers. This may be very easy for many people. Here I just want to share with you the code to generate not only the first 100 prime numbers. but also any number of prime numbers.

Below is the code snippet:

//Helper class to generate prime numbers
var PrimeProcessor=(function(){
        var primeArray=[];

        function _isPrime(num){
                if(num<=1){
                        throw new Error("Number cannot be smaller than 2");
                }
                var status=true;
                if(num!==2&&num%2===0){
                        status=false;
                }else{
                        for(var i=2;i<num;++i){
                                if(num%i==0){
                                        status=false;
                                        break;
                                }
                        }
                }
                return status;
        }

        return {
                generate:function(n){
                        var count=0,currentNum=2;
                        while(count<n){
                                if(_isPrime(currentNum)){
                                        primeArray.push(currentNum);
                                        count++;
                                }
                                currentNum++;
                        }
                        return primeArray;
                },
                display:function(primeArray){
                        console.log(primeArray.join(","));
                }
        };
})();

//Here 100 can be replace with N, N is any positive integer
PrimeProcessor.display(PrimeProcessor.generate(100));
console.log("Prime numbers generated successfully");

Here you only need to pass the number of prime numbers to be generated into PrimeProcessor.generate() method.

The algorithm for checking whether a number is a prime number is not optimized here. It first checks whether the number is 2 and whether it can be divided by 2. We know all even numbers except 2 are not prime numbers, so this can filter all the even numbers except 2. For more about checking whether a number is a prime number, please check this thread.

Here is the output:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541
Prime numbers generated successfully

This script can be run on both front and back end.

JAVASCRIPT ALGORITHM NODEJS PRIME NUMBER COURSERA

  SAVE AS PDF   MARK AS READ   MARK AS IMPORTANT

Share on Facebook  Share on Twitter  Share on Google+  Share on Weibo  Share on Reddit  Share on Digg  Share on Tumblr    Delicious

  RELATED


  5 COMMENTS


Matt [Reply]@ 2013-06-30 01:50:59

On line 13, in the condition of your for loop, it is only necessary to go up to sqrt(n)

Matt [Reply]@ 2013-06-30 01:53:46

This is because any potential divisor greater than sqrt(n) would also require a divisor less then sqrt(n)

NightCat [Reply]@ 2013-06-30 01:57:58

Yes, Matt. You are correct.

hugo luo [Reply]@ 2013-06-30 21:07:45

Line 10 :the decision condication is not very correct´╝ü

NightCat [Reply]@ 2013-06-30 22:11:58

What's wrong with that condition?


  WRITE ARTICLE

Santa in Beijing after a busy day

By sonic0002
It's a sarcastic picture describing how heavy the haze is in Beijing on Christmas day. Every winter people in Beijing will suffer the heavy haze.