Recently one of my friends mentioned a coding problem where the 1001^{th} prime needs to be found out. Out of many ways to achieve the answer, I used the elimination method which probably you would have used in the elementary school. Formally, this method is known as Sieve of Eratosthenes. When the position of the prime needs to be found out this approach is pretty simple and straightforward.

Following is how the problem is solved:

The 1001^{th} prime is **7927**

The source code can be used to find out any n^{th} prime.

However the *time efficiency* of this algorithm is in order of **n!** which means for higher upper limit, this method is extremely slower.

Check the code which is self explanatory.

class prime{ constructor(){ } getPrimes(limit){ let arr = this.createList(limit); let primes = this.savePrimes(arr); return primes; } createList(max){ let numberList = []; for (let i=2; i<=max; i++) { numberList.push(i); } return numberList; } savePrimes(numArr){ let i, j; for (i=0; i < numArr.length; i++){ let x = numArr[i]; for (j=i+1; j < numArr.length; j++ ){ let y = numArr[j]; let r = y%x; if(r==0){ numArr[j] = null; } } numArr = this.removeZeros(numArr); } return numArr; } removeZeros(numArr){ let newArr = []; for (let x in numArr){ let e = numArr[x]; if(e!=null){ newArr.push(e); } } return newArr; } } let obj = new prime(); let primeNumbers = obj.getPrimes(10000); console.log(primeNumbers[1000]);

Advertisements