Почему мое сито не подходит для поиска простых чисел?

Question

Я написал две основные функции поиска, и сито работает только на 10% лучше. Я использую две оптимизации для простой версии.

• Не проверять четные числа
• Проверять только до квадрата root или j * j <= i. (эквивалент)

и одна оптимизация для версии сита

• Проверьте только до квадрата root или i * i <= n. (эквивалент)

Какие оптимизации я могу добавить к сита?

Мое сито довольно медленное. Я пока не хочу делать побитовую реализацию, я хочу понять, дает ли эта реализация какие-либо преимущества.

Или если я пропустил точку реализации.

Внутренняя for l oop в псевдокоде выглядит здесь интересно / нечетно

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Я не знаю, как это интерпретировать. ( обновление: OP, по-видимому, указывает в комментариях, что это была проблема с неправильным форматированием после вставки копии псевдокода из Википедии, и с исправленным форматированием теперь ясно)

Вот оно:

алгоритм Сито Эратосфена is :

<strong>input:</strong> an integer <em>n</em> > 1.
<strong>output:</strong> all prime numbers from 2 through <em>n</em>.<br>
<strong>let</strong> <em>A</em> be an <strong>array of Boolean</strong> values, indexed by <strong>integers</strong> 2 to <em>n</em>,
initially all <strong>set</strong> to <strong>true</strong>.<br>
<strong>for</strong> <em>i</em> = 2, 3, 4, ..., not exceeding √n <strong>do</strong>
    <strong>if</strong> <em>A</em>[<em>i</em>] <strong>is true</strong>
        <strong>for</strong> <em>j</em> = <em>i<sup>2</sup>, i<sup>2</sup>+i, i<sup>2</sup>+2i, i<sup>2</sup>+3i, ...,</em> not exceeding <em>n</em> <strong>do</strong>
            <em>A</em>[<em>j</em>] := <strong>false</strong><br>
<strong>return</strong> all <em>i</em> such that <em>A</em>[<em>i</em>] is <strong>true</strong>. 

// prime-2
// 2 optimizations - odds and square root
function prime2(n){
  const primes = [2];
  not_prime: for(let i = 3; i < n; i += 2){
    for(let j = 2; j * j <= i; j++){
      if(i % j === 0){
        continue not_prime;
      }
    }
    primes.push(i);
  }
  return primes;
}

// prime-3
// sieve implementation
function prime3 (n) {
  const primes = [];
  const sieve = (new Array(n)).fill(true);
  for (let i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      for (let j = i + i; j < n; j += i) {
        sieve[j] = false;
      }
    }
  }
  makePrimes(sieve, primes, n);
  return primes;
};
function makePrimes(sieve, primes, n){
  for (let i = 2; i < n; i++) {
    if(sieve[i]) {
      primes.push(i);
    }
  }
}

Answer 1

То, что вы видите, является выражением различий в теоретических сложностях времени выполнения, то есть истинных алгоритмах c различий между двумя алгоритмами.

Оптимальная сложность решета с пробным делением равна O (n ^1,5 / (log n) ² ) ^(*) , тогда как для сита Эратосфена 'сложность составляет O ( n log log n) .

Согласно эмпирическим данным времени выполнения, опубликованным Скоттом Сойетом в комментариях ,

   1e6      279ms      36ms
   1e7     6946ms     291ms
   -------------------------
   n^       1.40       0.91

эмпирические порядки роста примерно равны ~ n ^1,4 и ~ n в измеренном диапазоне, что хорошо подходит.

Так что ваше подлинное сито работает хорошо. Сито , пробное деление работает как положено. * * * * * * Алгоритм c природы кода всегда будет превосходить любое присутствие или отсутствие любых вторичных оптимизаций, если мы достаточно увеличим размер задачи.

И сравниваем производительность, измеряя их только в одном Точка размера проблемы никогда недостаточно. Таким образом, даже если вы увидите разницу в 10% по сравнению с «более простой», если вы будете тестировать на больших размерах, разница будет больше.

---

Если вы хотите несколько советов о том, что можно улучшить в ваш код, обратите внимание, что вы начинаете внутренний l oop с i+i вместо i*i, для начинающих.

Другая распространенная оптимизация - это специальный случай 2 , начните с 3 и увеличьте число кандидатов на 2 и используйте внутреннее увеличение l oop 2*i вместо просто i, для достижения мгновенного ускорения в 2 раза. Это простейшая форма факторизации колеса оптимизации, которая может быть применена в дальнейшем, с уменьшением отдачи, хотя для каждого дополнительного простого числа. Но использование 2-3-5-7 является обычным делом и должно дать примерно еще 2-кратное ускорение, если память работает.

Последнее, но не менее важное: сделать это сегментировано .

---

^(*) это π(n)* π(√n) из простых чисел и не более чем из композитов.