Сито Эратосфена с Факторизацией Колеса
Я реализую достаточно быстрый генератор простых чисел, и я получил несколько хороших результатов с несколькими оптимизациями на основе эратосфена. В частности, во время предварительной части алгоритма я пропускаю все кратные 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.
Я уже прочитал много документации об этом, но я не видел никакой реализации с решеткой эратосфена … пример кода мог бы сильно помочь, но некоторые советы были бы полезны 🙂
Благодарю.
Решение
Вы можете пойти еще дальше. Вот некоторый код 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 допускает для циклического связанного списка.
Другие решения
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
Пол Притчард, австралийский математик, работающий в IBM, разработал серию колесных сит в 1980-х годах. Я обсуждаю один из них в мой блог, включая примеры, отработанные вручную, и реализацию в схеме. Это слишком велико, чтобы обсуждать здесь. Вы должны знать, что, хотя сложность асимптотики меньше, чем сита Эратосфена, детали реализации обычно делают ее медленнее на практике.
Существует гораздо лучшая оптимизация (для вашего варианта требуется O (n) операций вместо O (n log log n)): https://stackoverflow.com/a/17550147/2559094 , но это занимает больше памяти (использует n + n / log n памяти вместо n).
Если вы все еще хотите продолжить оптимизацию и рассмотреть простые числа p1, p2, …, pn, вы должны написать все числа от 0 до p1 * p2 * … * pn (используйте lcm, если вы решили не использовать только простые числа) и проверьте, какие из них удовлетворяют следующей системе:
х! = 0 (мод р1)
х! = 0 (мод р2)
…
x! = 0 (мод pn)
Затем вы должны найти все промежутки между этими числами и составить массив этих пробелов, чтобы использовать их.