Generate first N prime numbers

  sonic0002        2013-06-29 22:08:22       12,009        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 

       

  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?



  RANDOM FUN

MySQL - Postgres - Hadoop