Сито эратосфенов с фазообразованием колес

Question

Я реализую достаточно быстрый генератор простых чисел, и я получил неплохие результаты с несколькими оптимизациями на сите эратосфенов. В частности, в ходе предварительной части алгоритма, я пропустить все кратные 2 и 3 таким образом:

template<class Sieve, class SizeT> 
void PrimeGenerator<Sieve, SizeT>::factorize() 
{ 
    SizeT c = 2; 
    m_sieve[2] = 1; 
    m_sieve[3] = 1; 

    for (SizeT i=5; i<m_size; i += c, c = 6 - c) 
     m_sieve[i] = 1; 
} 

Здесь m_sieve является булевым массивом в соответствии с решетом Эратосфена. Я думаю, что это своего рода факторизация колес только с учетом простых чисел 2 и 3, увеличивающихся по образцу 2, 4, 2, 4, .. Что бы я хотел сделать, так это реализовать большее колесо, возможно, с учетом чисел 2,3 и 5. Я уже прочитал много документации об этом, но я не видел никакой реализации с ситом eratosthenes ... пример кода мог бы помочь много, но и некоторые подсказки были бы приятными :) Спасибо.

Answer 1

Вы можете пойти еще дальше. Вот некоторые OCaml код, который я написал несколько лет назад:

let eratosthene borne = 
    let remove_multiples a lst = 
    let rec remmult multa li accu = function 
     []   -> rev accu 
     | head::tail -> 
      if multa = head 
      then remmult (a*(hd li)) (tl li) accu  tail 
      else remmult multa  li (head::accu) tail 
    in 
    remmult (a * a) lst [] lst 
    in 
    let rec first_primes accu ll = 
    let a = hd ll in 
    if a * a > borne then (rev accu) @ ll 
    else first_primes (a::accu) (remove_multiples a (tl ll)) 
    in 
    let start_list = 
(* Hard code of the differences of consecutive numbers that are prime*) 
(* with 2 3 5 7 starting with 11... *) 
    let rec lrec = 2 :: 4 :: 2 :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 6 
     :: 6 :: 2 :: 6 :: 4 :: 2 :: 6 :: 4 :: 6 :: 8 :: 4 :: 2 :: 4 :: 2 
     :: 4 :: 8 :: 6 :: 4 :: 6 :: 2 :: 4 :: 6 :: 2 :: 6 :: 6 :: 4 :: 2 
     :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 2 :: 10 :: 2 :: 10 :: lrec 
    and listPrime2357 a llrec accu = 
     if a > borne then rev accu 
     else listPrime2357 (a + (num (hd llrec))) (tl llrec) (a::accu) 
    in 
    listPrime2357 (num 11) lrec [] 
    in 
    first_primes [(num 7);(num 5);(num 3);(num 2)] start_list;; 

Обратите внимание на хороший прием, который OCaml позволяет циклического связного списка.

Answer 2

Пол Притчард, австралийский математик, работающий в IBM, разработал серию колесных сит в 1980-х годах. Я обсуждаю один из них в my blog, включая примеры, выполненные вручную, и реализацию на Схеме. Здесь слишком много, чтобы обсудить здесь. Вы должны знать, что, хотя асимптотическая сложность меньше, чем сито Эратосфена, детали реализации обычно делают его более медленным на практике.

Answer 3

2 * 3 * 5 = 30
спиц = 2,3,4,5,6,8,9,10,12,15,16,18,20,24,30
числа между спицами: 1,7,11,13,17,19,23,25,29

int[] gaps = [6,4,2,4,2,4,2,4]; 
int[] primes = [2,3,5]; 
int max = 9001; 
int counter, max_visited; 
while(max_visited < max) { 
    int jump = gaps[counter]; 
    counter = counter + 1 % gaps.length; 
    max_visited += jump; 
} 

Помогло ли это?

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

primes = [2,3,5]; 
product = multiply(primes);//imaginary function that returns 30 
wheel = new int[product]; 
foreach(prime in primes) 
    for(int x = 1; x <= product/prime; x++) 
    wheel[prime*x] = 1; 
return wheel 

Answer 4

Там гораздо лучше оптимизации его (она занимает O (п) операций вместо O (N журнал журнал п) для вашего варианта): https://stackoverflow.com/a/17550147/2559094, но он занимает больше памяти (использует n + n/log n memory вместо n).

Если вы все еще хотите продолжить свою оптимизацию и считаете простые числа p1, p2, ..., pn, вы должны записать все числа от 0 до p1 * p2 * ... * pn (используйте lcm на случай, если вы решили использовать не только простые числа) и проверить, какие из них удовлетворяют следующей системе: x! = 0 (mod p1) x! = 0 (mod p2) ... x! = 0 (mod pn)

Затем вы должны найти все промежутки между этими числами и создать массив этих пробелов для их использования.