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

标签 javascript algorithm

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

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?

我解决了这个问题,在我保存 cousins 的数组中,当它达到 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);

最佳答案

欧拉筛,Pham 知道这个:) 12ms

Uchu,我没看到你的代码在哪里标记了倍数。这不是埃拉托色尼筛法应该做的吗?

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

关于javascript - 用 O(n) 求解第七个,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48897706/

相关文章:

algorithm - 没有前瞻性的桶之间的加权分布

algorithm - 如何在网格中找到所有可能的唯一路径?

algorithm - 最小瓶颈生成树与最小生成树有何不同?

javascript - AngularJS : having multiple functions in a controller

javascript - Ionic/Angular,将 JSON/Array 值作为 HTML 传递

javascript - 如何在 JavaScript 中引用 setInterval() id 本身,而不需要外部作用域的帮助?

java - java中链表实现的算法

python - 在 Python 中第一次出现模式时搜索 1GB+ 数据字符串的最快方法

javascript - 当视口(viewport)小于 480 时,图像源发生变化

javascript - 在不使用 html 的情况下为文本着色