Finding nth prime number – JavaScript

Recently one of my friends mentioned a coding problem where the 1001th 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 1001th prime is 7927
The source code can be used to find out any nth 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

Please add your valuable idea below, will make a discussion, thanks !

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s