javascript - 用O(n)求解第七个

我已经解决了seventh problem of Euler，它说:



我使用来解决它，并且在我保留表兄弟的数组中，当它达到10001的长度时，我返回了该数字。该算法需要 1300毫秒，我认为效率很低，我在实现中特别做什么？

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);

最佳答案

Euler筛子，Pham知道这一点:) 12ms

Uchu，我看不到您的代码在哪里标记倍数。那不是Eratosthenes筛子应该做的吗？

JavaScript代码(此代码实际上是btilly对code的改编，优化了我的想法):

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
  }
}