Алгоритм решета Эратосфена в JavaScript работает бесконечно для большого числа

Question

Я пытался написать алгоритм Sieve of Eratosthenes в JavaScript. В основном я просто буквально следовал за шагами ниже:

1. Создать список последовательных целых чисел от 2 до (п-1)
2. Пусть первое простое число р равно 2
3. Начиная с р, подсчитывают с шагом р и удаляет каждые из этих чисел (р и кратных р)
4. Перейти к следующему номеру в списке и повторите 2,3,4
5. Добавить случайное удаление простых чисел обратно в список

и это то, что я придумал:

function eratosthenes(n){ 
var array = []; 
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,... 
var maxPrimeFactor = 0; 
var upperLimit = Math.sqrt(n); 
var output = []; 

// Eratosthenes algorithm to find all primes under n 

// Make an array from 2 to (n - 1) 
//used as a base array to delete composite number from 
for(var i = 2; i < n; i++){ 
    array.push(i); 
} 

// Remove multiples of primes starting from 2, 3, 5,... 
for(var i = array[0]; i < upperLimit; i = array[0]){ 
    removeMultiples: 
    for(var j = i, k = i; j < n; j += i){ 
     var index = array.indexOf(j); 
     if(index === -1) 
      continue removeMultiples; 
     else 
      array.splice(index,1); 
    } 
    tmpArray.push(k); 
} 
array.unshift(tmpArray); 
return array; 
} 

Он работает для небольших чисел, но не для чисел больше, чем один миллион. Я использовал Node.js для тестирования, и процесс просто кажется бесконечным, и ошибка памяти не появилась. Я прочитал решение here (также в javascript), но все еще не могу его полностью понять.

Вопрос: Как сделать эту работу для достаточно больших чисел, таких как миллион и выше?

Answer 1

Вы делаете сито Эратосфена намеренно медленнее, используя функции манипуляции с массивами, такие как Array#indexOf и Array#splice, которые работают в линейном времени. Когда у вас может быть O (1) для обеих задействованных операций.

Ниже решета Эратосфена следующих обычных методов программирования:

var eratosthenes = function(n) { 
    // Eratosthenes algorithm to find all primes under n 
    var array = [], upperLimit = Math.sqrt(n), output = []; 

    // Make an array from 2 to (n - 1) 
    for (var i = 0; i < n; i++) { 
     array.push(true); 
    } 

    // Remove multiples of primes starting from 2, 3, 5,... 
    for (var i = 2; i <= upperLimit; i++) { 
     if (array[i]) { 
      for (var j = i * i; j < n; j += i) { 
       array[j] = false; 
      } 
     } 
    } 

    // All array[i] set to true are primes 
    for (var i = 2; i < n; i++) { 
     if(array[i]) { 
      output.push(i); 
     } 
    } 

    return output; 
}; 

You can see a live example for n = 1 000 000 here.

Answer 2

Этот вопрос немного скуп на низкой стороне в определении того, что такое «большое количество» есть и принимает что он начинается всего с миллиона, для которого работает current answer; однако он использует довольно много памяти, как в одном 8-байтовом номере (двойной реальный из 64 бит) для каждого просеиваемого элемента и еще одного 8-байтового числа для каждого найденного простого. Этот ответ не будет работать для «больших чисел», скажем, около 250 миллионов и выше, поскольку он будет превышать объем памяти, доступный для исполняющей машины JavaScript.

Следующий код JavaScript, реализующий «бесконечное» (неограниченное) Страница Сегментированное сито Эратосфена, преодолевает эту проблему, поскольку он использует только один бит-бит 16-ти килобайтного сегментированного просеивающего буфера (один бит представляет собой одно потенциальное простое число) и только использует память для базовых простых чисел до квадратного корня из текущего наибольшего числа в текущем сегменте страницы, причем фактические найденные простые числа перечислены в порядке, не требуя хранения; Кроме экономии времени лишь просеивание нечетных композитов в качестве единственного даже простого числа 2:

var SoEPgClass = (function() { 
    function SoEPgClass() { 
    this.bi = -1; // constructor resets the enumeration to start... 
    } 
    SoEPgClass.prototype.next = function() { 
    if (this.bi < 1) { 
     if (this.bi < 0) { 
     this.bi++; 
     this.lowi = 0; // other initialization done here... 
     this.bpa = []; 
     return 2; 
     } else { // bi must be zero: 
     var nxt = 3 + 2 * this.lowi + 262144; //just beyond the current page 
     this.buf = []; 
     for (var i = 0; i < 2048; i++) this.buf.push(0); // faster initialization 16 KByte's: 
     if (this.lowi <= 0) { // special culling for first page as no base primes yet: 
      for (var i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p * p) 
      if ((this.buf[i >> 5] & (1 << (i & 31))) === 0) 
       for (var j = (sqr - 3) >> 1; j < 131072; j += p) 
       this.buf[j >> 5] |= 1 << (j & 31); 
     } else { // other than the first "zeroth" page: 
      if (!this.bpa.length) { // if this is the first page after the zero one: 
      this.bps = new SoEPgClass(); // initialize separate base primes stream: 
      this.bps.next(); // advance past the only even prime of 2 
      this.bpa.push(this.bps.next()); // keep the next prime (3 in this case) 
      } 
      // get enough base primes for the page range... 
      for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt; 
      p = this.bps.next(), this.bpa.push(p), sqr = p * p); 
      for (var i = 0; i < this.bpa.length; i++) { //for each base prime in the array 
      var p = this.bpa[i]; 
      var s = (p * p - 3) >> 1; //compute the start index of the prime squared 
      if (s >= this.lowi) // adjust start index based on page lower limit... 
       s -= this.lowi; 
      else { //for the case where this isn't the first prime squared instance 
       var r = (this.lowi - s) % p; 
       s = (r != 0) ? p - r : 0; 
      } 
      //inner tight composite culling loop for given prime number across page 
      for (var j = s; j < 131072; j += p) this.buf[j >> 5] |= 1 << (j & 31); 
      } 
     } 
     } 
    } 
    //find next marker still with prime status 
    while (this.bi < 131072 && this.buf[this.bi >> 5] & (1 << (this.bi & 31))) .bi++; 
    if (this.bi < 131072) // within buffer: output computed prime 
     return 3 + ((this.lowi + this.bi++) * 2); 
    else { // beyond buffer range: advance buffer 
     this.bi = 0; 
     this.lowi += 131072; 
     return this.next(); // and recursively loop just once to make a new page buffer 
    } 
    }; 
    return SoEPgClass; 
})(); 

Приведенных выше код может быть использован для подсчета простых чисел до заданного предела с помощью следующего кода JavaScript:

window.onload = function() { 
    var elpsd = -new Date().getTime(); 
    var top_num = 1000000000; 
    var cnt = 0; 
    var gen = new SoEPgClass(); 
    while (gen.next() <= top_num) cnt++; 
    elpsd += (new Date()).getTime(); 
    document.getElementById('content') 
    .innerText = 'Found ' + cnt + ' primes up to ' + top_num + ' in ' + elpsd + ' milliseconds.'; 
}; 

Если вышеуказанные два фрагмента кода JavaScript помещаются в файл с именем app.js в той же папке, что и следующий HTML-код, который называется any.HTML, вы будете иметь возможность запускать код в вашем браузере, открыв файл HTML в нем:

<!DOCTYPE html> 

<html lang="en"> 
    <head> 
    <meta charset="utf-8" /> 
    <title>Page Segmented Sieve of Eratosthenes in JavaScript</title> 
    <script src="app.js"></script> 
    </head> 
    <body> 
    <h1>Page Segmented Sieve of Eratosthenes in JavaScript.</h1> 

    <div id="content"></div> 
    </body> 
</html> 

Этот код может просеивать на один миллиард диапазона несколько 10-х секунд при запуске на исполнение двигателя JavaScript используя компиляцию Just-In-Time (JIT), такую ​​как движок V8 от Google Chrome. Дальнейшие успехи могут быть достигнуты за счет использования экстремальной факторизации колес и предварительной отбраковки буферов страниц наименьших базовых простых чисел, и в этом случае объем выполненной работы может быть сокращен еще на четыре раза, что означает, что количество простых чисел можно подсчитать до миллиарда в несколько секунд (подсчет не требует перечисления, как используется здесь, а скорее может использовать таблицы подсчета счетчика бит на буфера сегментов страницы напрямую), хотя ценой повышенной сложности кода.

Answer 3

Просто для удовольствия, я реализовал алгоритм решета Erastoten (работает с узлом), строго следуя правилам TDD. Эта версия должна быть достаточной для интервью, как школьное упражнение или так же, как и я, - для битвы.

Позвольте мне заявить, что я определенно считаю, что принятый ответ должен быть предоставлен GordonBGood.

module.exports.compute = function(size) 
{ 
    if (!utils.isPositiveInteger(size)) 
    { 
     throw new TypeError("Input must be a positive integer"); 
    } 

    console.time('optimal'); 
    console.log(); 
    console.log("Starting for optimal computation where size = " + size); 
    let sieve = utils.generateArraySeq(2, size); 

    let prime = 2; 
    while (prime) 
    { 
     // mark multiples 
     for (let i = 0; i < sieve.length; i += prime) 
     { 
      if (sieve[i] !== prime) 
      { 
       sieve[i] = -1; 
      } 
     } 

     let old_prime = prime; 
     // find next prime number 
     for (let i = 0; i < sieve.length; i++) 
     { 
      if ((sieve[i] !== -1) && (sieve[i] > prime)) 
      { 
       prime = sieve[i]; 
       break; 
      } 
     } 

     if (old_prime === prime) 
     { 
      break; 
     } 
    } 
    console.timeEnd('optimal'); 
    // remove marked elements from the array 
    return sieve.filter( 
     function(element) 
     { 
      return element !== -1; 
     }); 
} // compute 

Буду признателен за любую чувствительную критику.

The whole repository can be found on my github account.

Answer 4

Я бы этот пост в качестве комментария к Александру, но у меня нет репутации, чтобы сделать это. Его ответ потрясающий, и это просто улучшает его, чтобы сделать его быстрее. Я сравнивал результаты тестирования n = 100 000 000.

Вместо использования true и false в 'array', я получаю большое ускорение скорости с использованием 1 и 0. Это сократило мое время в Chrome с 5000 мс до 4250 мс. Firefox не был затронут (5600 мс в любом случае).

Тогда мы можем принять во внимание, что даже числа никогда не будут первыми. Поместите 2 в «выход» с бита, и вы можете сделать i = 3; i + = 2 и j + = i * 2 во время сита (мы можем пропустить четные кратные числа, так как любое число раз четное число четное), пока мы также i + = 2 при нажатии на 'output' на конец. Это сократило мое время в Chrome с 4250 мс до 3350 мс. Firefox выиграл чуть меньше, снизившись с 5600 мс до 4800 мс.

В любом случае, сочетание этих двух настроек дало мне 33% -ное повышение скорости в Chrome и 14% -ное увеличение в Firefox. Вот улучшенная версия кода Александра.

var eratosthenes = function(n) { 
    // Eratosthenes algorithm to find all primes under n 
    var array = [], upperLimit = Math.sqrt(n), output = [2]; 

    // Make an array from 2 to (n - 1) 
    for (var i = 0; i < n; i++) 
     array.push(1); 

    // Remove multiples of primes starting from 2, 3, 5,... 
    for (var i = 3; i <= upperLimit; i += 2) { 
     if (array[i]) { 
      for (var j = i * i; j < n; j += i*2) 
       array[j] = 0; 
     } 
    } 

    // All array[i] set to 1 (true) are primes 
    for (var i = 3; i < n; i += 2) { 
     if(array[i]) { 
      output.push(i); 
     } 
    } 

    return output; 
};