Сито Эратосфена с использованием предварительно рассчитанных простых чисел
У меня есть все простые числа, которые могут быть сохранены в 32-битной unsigned int а также Я хочу использовать их для генерации 64-битных простых чисел. использование пробного деления слишком медленное, даже с оптимизацией логики и компиляции.
Я пытаюсь изменить Sieve of Eratosthenes для работы с предопределенным списком следующим образом:
- в массиве А от 2 до 4294967291
- в массиве B от 2 ^ 32 до X, включая 1
- найти C, который является первым кратным текущего простого числа.
- от отметки C и переход на текущее простое число до X.
- перейти к 1.
Проблема в шаге 3, который использует модуль для нахождения простого множителя, такая операция — причина, по которой я не использовал разделение следов.
Есть ли лучший способ реализовать шаг 3 или весь алгоритм.
благодарю вас.
Решение
Увеличивайте на 2, а не на 1. Это минимальная оптимизация, которую вы всегда должны использовать — работа только с коэффициентами. Не нужно беспокоиться о вечерах.
В C ++ используйте vector<bool> для ситового массива. Это автоматически упаковано.
Предварительно рассчитайте основные числа с помощью сегментированного сита. Затем продолжайте работать с достаточно большими сегментами, которые помещаются в ваш кеш, без добавления новых простых чисел в основной список. Для каждого простого p поддерживать дополнительные long long int value: его текущий кратный (начиная с квадрата простого числа, конечно). Значение шага дважды p в стоимости, или p смещение в массиве сит, упакованном с учетом шансов, где i-ая запись обозначает номер o + 2i, o будучи наименее странным, не ниже начала диапазона. Нет необходимости сортировать по значениям кратных, верхняя граница использования основных простых чисел монотонно возрастает.
sqrt (0xFFFFFFFFFF) = 1048576. PrimePi (1048576) = 82025 простые числа — все, что вам нужно в вашем основном списке простых чисел. Это арахис.
Целочисленная арифметика для long long ints должен работать просто отлично, чтобы найти модуль и, следовательно, наименьшее кратное в диапазоне, когда вы начинаете (или возобновляете свою работу).
Смотрите также связанный ответ псевдокодом, а также другой с кодом C.
Другие решения
Других решений пока нет …