Сегментированное сито эратосфена?

Ответ 1

Основная идея сегментированного сита состоит в том, чтобы выбирать просеивающие пробы меньше квадратного корня из n, выбирать достаточно большой размер сегмента, который, тем не менее, помещается в память, а затем просеивать каждый из сегментов по очереди, начиная с наименьшего, В первом сегменте вычисляется наименьшее кратное каждого просеивания просеивания, которое находится внутри сегмента, а затем кратность просеивания просеивания обозначаются как составные обычным способом; когда используются все просеивающие простые числа, оставшиеся немаркированные номера в сегменте являются первичными. Затем, для следующего сегмента, для каждого просеивающего праймера вы уже знаете первый множественный номер в текущем сегменте (это был кратный, который закончил просеивание для этого штриха в предыдущем сегменте), так что вы просеиваете на каждом просеивании, и так далее пока вы не закончите.

Размер n не имеет значения, за исключением того, что большее n будет занимать больше времени, чем меньшее n; размер которого имеет значение, - это размер сегмента, который должен быть как можно большим (например, размер кеша первичной памяти на машине).

Вы можете увидеть простую реализацию сегментированного сита здесь. Обратите внимание, что сегментированное сито будет намного быстрее, чем сито с приоритетом О'Ней, упомянутое в другом ответе; если вам интересно, там реализована реализация .

EDIT: Я написал это для другой цели, но я покажу его здесь, потому что это может быть полезно:

Хотя сито Эратосфена очень быстро, оно требует O (n) пространства. Это может быть сведено к O (sqrt (n)) для просеивающих простых чисел плюс O (1) для битаррей, выполняя просеивание в последовательных сегментах. В первом сегменте вычисляется наименьшее кратное каждого просеивания просеивания, которое находится внутри сегмента, а затем кратность просеивания просеивания помечены как составные в обычном порядке; когда используются все просеивающие простые числа, оставшиеся немаркированные номера в сегменте являются первичными. Затем для следующего сегмента наименьшее кратное каждого просеивания является кратным, которое закончило просеивание в предыдущем сегменте, и поэтому просеивание продолжается до завершения.

Рассмотрим пример сита от 100 до 200 в сегментах 20. Пять просеивающих простых чисел - 3, 5, 7, 11 и 13. В первом сегменте от 100 до 120 биткрайр имеет десять слотов со слотом 0 соответствующий 101, слот k, соответствующий 100 + 2k + 1, и слот 9, соответствующий 119. Наименьший кратный 3 в сегменте равен 105, соответствующий слоту 2; слоты 2 + 3 = 5 и 5 + 3 = 8 также кратные 3. Наименьшее кратное 5 равно 105 в слоте 2, а слот 2 + 5 = 7 также кратно 5. Наименьшее кратное 7 равно 105 в слоте 2, а слот 2 + 7 = 9 также кратен 7. И так далее.

Функция primesRange принимает аргументы lo, hi и delta; lo и hi должны быть четными, причем lo < hi и lo должно быть больше, чем sqrt (hi). Размер сегмента в два раза больше. Ps - это связанный список, содержащий просеивающие простые числа меньше, чем sqrt (hi), причем 2 удалены, так как четные числа игнорируются. Qs является связанным списком, содержащим вредоносное ПО в битвейере сита наименьшего кратного в текущем сегменте соответствующего просеивания. После каждого сегмента lo продвигается на удвоенную дельта, поэтому число, соответствующее индексу я решетчатого битрейма, равно lo + 2i + 1.

function primesRange(lo, hi, delta)
    function qInit(p)
        return (-1/2 * (lo + p + 1)) % p
    function qReset(p, q)
        return (q - delta) % p
    sieve := makeArray(0..delta-1)
    ps := tail(primes(sqrt(hi)))
    qs := map(qInit, ps)
    while lo < hi
        for i from 0 to delta-1
            sieve[i] := True
        for p,q in ps,qs
            for i from q to delta step p
                sieve[i] := False
        qs := map(qReset, ps, qs)
        for i,t from 0,lo+1 to delta-1,hi step 1,2
            if sieve[i]
                output t
        lo := lo + 2 * delta

Когда вызывается как primesRange (100, 200, 10), просеивающие числа ps являются [3, 5, 7, 11, 13]; qs первоначально [2, 2, 2, 10, 8], соответствующих наименьшим кратным 105, 105, 105, 121 и 117, и составляет reset для второго сегмента [1, 2, 6, 0, 11], соответствующего до наименьших кратных 123, 125, 133, 121 и 143.

Вы можете увидеть эту программу в действии на http://ideone.com/iHYr1f a > . И в дополнение к ссылкам, показанным выше, если вы заинтересованы в программировании с помощью простых чисел, я скромно рекомендую этот эссе в своем блоге.

Ответ 2

Там версия Сита, основанная на очередях приоритетов, которая дает столько простых, сколько вы запрашиваете, а не все из них до верхней границы. Он обсуждался в классической статье "Подлинное сито Эратосфена" и googling для "решета очереди приоритетов eratosthenes" появляется довольно много реализаций в различных языки программирования.

Ответ 3

Просто мы делаем сегментирование с помощью решета, который у нас есть. Основная идея - сказать, что нам нужно найти простые числа от 85 до 100. Мы должны применять традиционное сито, но в порядке, как описано ниже:

Итак, возьмем первое простое число 2, разделим начальное число на 2 (85/2) и округляя до меньшего числа, получим p = 42, теперь снова умножим на 2, получим p = 84, далее отсюда начните добавлять 2 до последнего номера. Итак, мы сделали, что мы удалили все коэффициенты 2 (86,88,90,92,94,96,98,100) в диапазоне.

Возьмем следующее простое число 3, разделим начальное число на 3 (85/3) и завершим на меньшее число, получим p = 28, теперь снова умножим на 3, получим p = 84, начиная с этого начала добавив 3 до последнего номера. Итак, мы сделали то, что мы удалили все факторы из 3 (87,90,93,96,99) в диапазоне.

Возьмем следующее простое число = 5 и т.д................... Продолжайте выполнение вышеуказанных шагов. Вы можете получить простые числа (2,3,5,7,...), используя традиционное сито до sqrt (n). Затем используйте его для сегментированного сита.

Ответ 4

На основании ответа Swapnil Kumar я выполнил следующий алгоритм в C. Он был создан с помощью mingw32-make.exe.

#include<math.h>
#include<stdio.h>
#include<stdlib.h>

int main()
{
    const int MAX_PRIME_NUMBERS = 5000000;//The number of prime numbers we are looking for
    long long *prime_numbers = malloc(sizeof(long long) * MAX_PRIME_NUMBERS);
    prime_numbers[0] = 2;
    prime_numbers[1] = 3;
    prime_numbers[2] = 5;
    prime_numbers[3] = 7;
    prime_numbers[4] = 11;
    prime_numbers[5] = 13;
    prime_numbers[6] = 17;
    prime_numbers[7] = 19;
    prime_numbers[8] = 23;
    prime_numbers[9] = 29;
    const int BUFFER_POSSIBLE_PRIMES = 29 * 29;//Because the greatest prime number we have is 29 in the 10th position so I started with a block of 841 numbers
    int qt_calculated_primes = 10;//10 because we initialized the array with the ten first primes
    int possible_primes[BUFFER_POSSIBLE_PRIMES];//Will store the booleans to check valid primes
    long long iteration = 0;//Used as multiplier to the range of the buffer possible_primes
    int i;//Simple counter for loops
    while(qt_calculated_primes < MAX_PRIME_NUMBERS)
    {
        for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++)
            possible_primes[i] = 1;//set the number as prime

        int biggest_possible_prime = sqrt((iteration + 1) * BUFFER_POSSIBLE_PRIMES);

        int k = 0;

        long long prime = prime_numbers[k];//First prime to be used in the check

        while (prime <= biggest_possible_prime)//We don't need to check primes bigger than the square root
        {
            for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++)
                if ((iteration * BUFFER_POSSIBLE_PRIMES + i) % prime == 0)
                    possible_primes[i] = 0;

            if (++k == qt_calculated_primes)
                break;

            prime = prime_numbers[k];
        }
        for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++)
            if (possible_primes[i])
            {
                if ((qt_calculated_primes < MAX_PRIME_NUMBERS) && ((iteration * BUFFER_POSSIBLE_PRIMES + i) != 1))
                {
                    prime_numbers[qt_calculated_primes] = iteration * BUFFER_POSSIBLE_PRIMES + i;
                    printf("%d\n", prime_numbers[qt_calculated_primes]);
                    qt_calculated_primes++;
                } else if (!(qt_calculated_primes < MAX_PRIME_NUMBERS))
                    break;
            }

        iteration++;
    }

    return 0;
}

Он задает максимум простых чисел, которые нужно найти, затем массив инициализируется известными простыми числами, такими как 2, 3, 5... 29. Таким образом, мы создаем буфер, который будет хранить сегменты возможных простых чисел, этот буфер не может быть больше мощности наибольшего начального штриха, который в этом случае равен 29.

Я уверен, что есть много оптимизаций, которые можно сделать для повышения производительности, например, распараллеливать процесс анализа сегментов и пропускать числа, кратные 2, 3 и 5, но это служит примером низкого потребления памяти.

Ответ 5

Если кто-то хочет увидеть реализацию на С++, вот моя:

void sito_delta( int delta, std::vector<int> &res)
{

std::unique_ptr<int[]> results(new int[delta+1]);
for(int i = 0; i <= delta; ++i)
    results[i] = 1;

int pierw = sqrt(delta);
for (int j = 2; j <= pierw; ++j)
{
    if(results[j])
    {
        for (int k = 2*j; k <= delta; k+=j)
        {
            results[k]=0;
        }
    }
}

for (int m = 2; m <= delta; ++m)
    if (results[m])
    {
        res.push_back(m);
        std::cout<<","<<m;
    }
};
void sito_segment(int n,std::vector<int> &fiPri)
{
int delta = sqrt(n);

if (delta>10)
{
    sito_segment(delta,fiPri);
   // COmpute using fiPri as primes
   // n=n,prime = fiPri;
      std::vector<int> prime=fiPri;
      int offset = delta;
      int low = offset;
      int high = offset * 2;
      while (low < n)
      {
          if (high >=n ) high = n;
          int mark[offset+1];
          for (int s=0;s<=offset;++s)
              mark[s]=1;

          for(int j = 0; j< prime.size(); ++j)
          {
            int lowMinimum = (low/prime[j]) * prime[j];
            if(lowMinimum < low)
                lowMinimum += prime[j];

            for(int k = lowMinimum; k<=high;k+=prime[j])
                mark[k-low]=0;
          }

          for(int i = low; i <= high; i++)
              if(mark[i-low])
              {
                fiPri.push_back(i);
                std::cout<<","<<i;
              }
          low=low+offset;
          high=high+offset;
      }
}
else
{

std::vector<int> prime;
sito_delta(delta, prime);
//
fiPri = prime;
//
int offset = delta;
int low = offset;
int high = offset * 2;
// Process segments one by one 
while (low < n)
{
    if (high >= n) high = n;
    int  mark[offset+1];
    for (int s = 0; s <= offset; ++s)
        mark[s] = 1;

    for (int j = 0; j < prime.size(); ++j)
    {
        // find the minimum number in [low..high] that is
        // multiple of prime[i] (divisible by prime[j])
        int lowMinimum = (low/prime[j]) * prime[j];
        if(lowMinimum < low)
            lowMinimum += prime[j];

        //Mark multiples of prime[i] in [low..high]
        for (int k = lowMinimum; k <= high; k+=prime[j])
            mark[k-low] = 0;
    }

    for (int i = low; i <= high; i++)
        if(mark[i-low])
        {
            fiPri.push_back(i);
            std::cout<<","<<i;
        }
    low = low + offset;
    high = high + offset;
}
}
};

int main()
{
std::vector<int> fiPri;
sito_segment(1013,fiPri);
}