Сито Эратосфена с Факторизацией Колеса

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. Я уже прочитал много документации об этом, но я не видел никакой реализации с решеткой эратосфена... пример кода мог бы помочь, но некоторые советы были бы хороши:) Спасибо.

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-х годах. Я обсуждаю один из них в своем блоге, включая примеры, отработанные вручную, и реализацию в Схеме. Это слишком велико, чтобы обсуждать здесь. Вы должны знать, что, хотя асимптотическая сложность меньше, чем сито Эратосфена, детали реализации обычно делают ее медленнее на практике.

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(n) операций вместо O(n log log n)): /questions/17872004/kolichestvo-razlichnyih-prostyih-faktorov-chisla/17872016#17872016, но для этого требуется больше памяти (используется n + n/log n памяти вместо n).

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

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