Finding the prime number. how to improve efficiency of my code

Question

So i am doing Euler problems, and i got to problem asking to find 10001st prime number. i did it like this. From what i can see it has O n^2. Codepen didnt like the time it took and thought it was an infinite loop, had to run on another compiler, my question is there anyway to improve this?

    isPrime=(num)=>{
  if(num<=1){
    return false;
  }
  for(let i=2;i<num;i++){
    if(num%i == 0){
      return false;
    }
  }
  return true;
}

findPrime=()=>{
  let count=0;
  let number  = 1;
  let prime=0;
  while(count != 10001){

    let result = isPrime(number);
    if(result === true){
       count++;
      prime = number;
       }
    number++;
  }
  return prime;
}

Look at this: [Number prime test in JavaScript](https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript) — 54ka, May 15 '20 at 04:42
also you don't need to run the loop till ```i < num```. Running till ````i < sqrt(num) + 1```` will do. — PR7, May 15 '20 at 04:48

score 0 · Answer 1 · answered May 15 '20 at 20:27

Takes around 1/60 time in node.js and around 1/140 here in Chrome comparing to your original without additional optimisations on my machine, but has a bit more complex setup...

var primes = [2, 3]; // lets start with some basic

function myPrimes(no, mapSize) {
  var nonPrimeMap = {};
  var pos = 0;
  var pos2 = 4;
  while (pos < no) {
    var s = primes[pos++];
    for (var x = s * 2; x < mapSize; x += s) nonPrimeMap[x] = 1;
    do {
      if (nonPrimeMap[pos2]) pos2++;
      else {
        primes.push(pos2++);
        break;
      }
    } while (true);
  }
}

function runTest() {
  var a = new Date();
  myPrimes(9999, 110000);
  var c = new Date();
  console.log(primes[primes.length - 1], c - a); // My test timespans in ms
  var b = findPrime();
  a = new Date();
  console.log(b, a - c); // Your
}

isPrime = (num) => {
  if (num <= 1) {
    return false;
  }
  for (let i = 2; i < num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
};

findPrime = () => {
  let count = 0;
  let number = 1;
  let prime = 0;
  while (count != 10001) {
    const result = isPrime(number);
    if (result === true) {
      count++;
      prime = number;
    }
    number++;
  }
  return prime;
};
runTest();

Finding the prime number. how to improve efficiency of my code

1 Answers1