Сито Эратосфена с использованием предварительно рассчитанных простых чисел
все простые числа, которые могут храниться в 32-битныхunsigned int
а такжеЯ хочу использовать их для генерации 64-битных простых чисел, использование пробного деления слишком медленное, даже с оптимизацией логики и компиляции.
Я пытаюсь изменить Sieve of Eratosthenes для работы с предопределенным списком, как показано ниже:
в массиве А от 2 до 4294967291в массиве B от 2 ^ 32 до X inc на 1найти C, который является первым кратным текущего простого числа.от отметки C и переход на текущее простое число до X.перейти к 1.Проблема в шаге 3, который использует модуль для нахождения простого множителя, такая операция - причина, по которой я не сделалт использовать разделение следа.
Есть ли лучший способ реализовать шаг 3 или весь алгоритм.
благодарю вас.