Today's Question:  What's your opinion about Alibaba mooncake incident?        GIVE A SHOUT

Technical Article => Programming =>  Algorithm

Generate first N prime numbers

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

  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

Why are human beings so dependent on Earth?

By sonic0002
Earth is the only home of human beings, at least for now. Why are people so dependent on Earth? The real reason is in the picture.