Today's Question:  What does your personal desk look like?        GIVE A SHOUT

Generate first N prime numbers

  sonic0002        2013-06-29 22:08:22       11,756        5    

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 

Share on Facebook  Share on Twitter  Share on Weibo  Share on Reddit 

  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?