Solving the seventh with O(n)

Question

I have solved the seventh problem of Euler, it says:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

I solved it using, and in the array in which I keep the cousins, when it reaches the length of 10001, I return that number. The algorithm takes 1300 ms, which I tink that is very inefficient, what am I doing particularly in my implementation?

var start = performance.now();

function eratosthenes(n) {
  var arr = [2], acc = 0; 
// matrix to save the found prime numbers and mark their multiples
  for(var i = 3; true; i += 2) { // loop
    if(arr.length === n) return arr[arr.length - 1]; // if the array length is equal to n return the last number
    if(!resolve(arr, i)) { // check if is multiple of the prime numbers, already found.
      arr.push(i); // if isnt multiple, save it
    }
  }
}

function resolve(array, n) {
  return array.some(cur => !(n%cur));
}
console.log(eratosthenes(10001)); // Tooks 1300 ms

var end = performance.now();
var time = end - start;

console.log(time);

Answer 1

Euler sieve, Pham knows this one :) 12ms

Uchu, I don't see where your code is marking the multiples. Isn't that what Sieve of Eratosthenes is supposed to do?

JavaScript code (this code is actually an adaptation of code by btilly, optimizing an idea of mine):

var start = performance.now();
n = 115000
a = new Array(n+1)
total = 0
s = []
p = 1
count = 0
while (p < n){
  p = p + 1

  if (!a[p]){
    count = count + 1
    if (count == 10001){
      console.log(p);
      end = performance.now();
      time = end - start;

      console.log(time);
      break;
    }
    a[p] = true
    s.push(p)

    limit = n / p
    new_s = []

    for (i of s){
      j = i
      while (j <= limit){
        new_s.push(j)
        a[j*p] = true;
        j = j * p
      }
    }
    s = new_s
  }
}

Answer 2

As requested by JaromandaX, this is the code for Sieve of Eratosthenes. 51 ms on my browser (OP solution is 750 ms)

var max = 1000000;

function eratosthenes(n) {
   var arr = [], count = 0;
   for (var i = 0; i < max; i++){
       arr.push(true);
   }
   for (var i = 2; i < max; i++){
       if(arr[i]){
 
           count++;
           if(count == n){
 
              return i;
           } 
           for (var j = i + i; j < max; j += i ){
                arr[j] = false;
           }
       }
   }
    
}
var start = performance.now(); 
console.log(eratosthenes(10001)); 
var end = performance.now();
var time = end - start;

console.log(time);

Answer 3

This has a similar running time to גלעד ברקן's answer (actually about 10% faster on my machine), but doesn't rely on knowing an approximate max before starting. It performs a seive of Eratosthenes up to max (starting at 2) and then doubles max, initialises the new elements in the array per the previously found primes and repeats.

function eratosthenes(n) {
    let prev_max = 1, max = 2, i, j;
    const primes = [], is_prime = new Array(max+1).fill(true);
    while( true ) {
      for ( i = prev_max + 1; i <= max; i++){
        if ( ! is_prime[i] ) continue;

        primes.push( i );

        if ( primes.length === n )
            return i;

        for ( j = i + i; j <= max; j += i )
            is_prime[j] = false;
      }

      const next_max = max*2;
      is_prime.length = next_max + 1;
      is_prime.fill( true, max + 1, next_max );

      for ( i = 0; i < primes.length; i++ ) {
        const prime = primes[i];
        for ( j = max + prime - max%prime; j <= next_max; j += prime )
          is_prime[j] = false;
      }
      prev_max = max;
      max = next_max;
   }
}

var start = performance.now(); 
console.log(eratosthenes(10001)); 
var end = performance.now();
var time = end - start;

console.log(time);

Answer 4

If it is a code-writing exercise, it is better to explore the earlier answers.

But if you are after a simple and fast solution, here's how you can solve it using prime-lib, which I created:

import {generatePrimes} from 'prime-lib';

const seekIndex = 10_001; // index of the prime being sought
const start = Date.now();
let a, c = 0;
const i = generatePrimes({boost: seekIndex + 1});
while ((a = i.next()) && !a.done && c++ < seekIndex) ;

console.log(`Prime: ${a.value}, took ${Date.now() - start}ms`);

On my PC it spits out:

Prime: 104759, took 5ms

And with the modern RXJS this becomes even simpler still:

import {generatePrimes} from 'prime-lib';
import {from, last} from 'rxjs';

const seekIndex = 10_001; // index of the prime being sought
const i = generatePrimes({boost: seekIndex + 1});
from(i).pipe(last()).subscribe(console.log);
//=> 104759