Рубрики

Сегментированное сито (печать простых чисел в диапазоне)

Учитывая диапазон [низкий, высокий], вывести все простые числа в этом диапазоне? Например, если заданный диапазон равен [10, 20], то выходной сигнал равен 11, 13, 17, 19.

Наивный подход заключается в запуске цикла от низкого до высокого и проверке каждого числа на простоту.

Лучший подход состоит в том, чтобы предварительно вычислить простые числа до максимального предела, используя сито Эратосфена , а затем распечатать все простые числа в диапазоне.

Вышеуказанный подход выглядит хорошо, но рассмотрим входной диапазон [50000, 55000]. Приведенный выше метод сита будет вычислять простые числа от 2 до 50100. Это приводит к пустой трате памяти и времени. Ниже представлен подход на основе сегментированного сита.

Сегментированное сито (фон)
Ниже приведены основные шаги, чтобы понять, как работает Segmented Sieve.

  1. Используйте Simple Sieve, чтобы найти все простые числа до заданного предела (в приведенном ниже коде используется квадратный корень из «high») и сохранить эти простые числа в массиве «prime []». В основном мы называем Simple Sieve для предела, и мы не только находим простые числа, но и помещаем их в отдельный массив prime [].
  2. Создайте метку массива [high-low + 1]. Здесь нам нужно только пространство O (n), где n — количество элементов в данном диапазоне.
  3. Переберите все простые числа, найденные в шаге 1. Для каждого простого числа отметьте его кратные в данном диапазоне [low..high].

Таким образом, в отличие от простого сита, мы не проверяем все кратные каждого числа, меньшего, чем квадратный корень из high, мы проверяем только кратные простые числа, найденные в шаге 1. И нам не нужно O (старшее) пространство, нам нужно O (sqrt (high) + n) пробел.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для распечатки всех простых чисел в диапазоне
// используя концепцию сегментированного сита
#include <bits/stdc++.h>

using namespace std;

  
// Эта функция находит все простые числа меньше предела
// используя простое сито из эратосфена. Это магазины найдено
// простые числа в векторном простом []

void simpleSieve(int limit, vector<int>& prime)

{

    bool mark[limit + 1];

    memset(mark, false, sizeof(mark));

  

    for (int i = 2; i <= limit; ++i) {

        if (mark[i] == false) {

            // Если еще не отмечено, то это простое число

            prime.push_back(i);

            for (int j = i; j <= limit; j += i)

                mark[j] = true;

        }

    }

}

  
// Находит все простые числа в заданном диапазоне, используя
// сегментированное сито

void primesInRange(int low, int high)

{

    // Вычисляем все простые числа, меньшие или равные

    // квадратный корень высокого с помощью простого сита

    int limit = floor(sqrt(high)) + 1;

    vector<int> prime;

    simpleSieve(limit, prime);

  

    // Количество элементов в заданном диапазоне

    int n = high - low + 1;

  

    // Объявляем логическое значение только для [low, high]

    bool mark[n + 1];

    memset(mark, false, sizeof(mark));

  

    // Используем найденные простые числа при помощи simpleSieve (), чтобы найти

    // простые числа в заданном диапазоне

    for (int i = 0; i < prime.size(); i++) {

        // Находим минимальное число в [low..high], которое

        // кратно простому [i] (делится на простое [i])

        int loLim = floor(low / prime[i]) * prime[i];

        if (loLim < low)

            loLim += prime[i];

        if(loLim==prime[i])

            loLim += prime[i];

        / * Пометить кратные простого числа [i] в [low..high]:

            Мы отмечаем j - низкий для j, то есть каждого числа

            в диапазоне [низкий, высокий] отображается на [0, высокий - низкий]

            поэтому, если диапазон [50, 100], маркировка 50 соответствует

            маркировке 0 маркировка 51 соответствует 1 и

            скоро. Таким образом, нам нужно только выделить место

            для диапазона * /

        for (int j = loLim; j <= high; j += prime[i])

            mark[j - low] = true;

    }

  

    // Числа, которые не отмечены в диапазоне, являются простыми

    for (int i = low; i <= high; i++)

        if (!mark[i - low])

            cout << i << "  ";

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int low = 10, high = 100;

    primesInRange(low, high);

    return 0;

}

питон

# Программа Python для печати распечатки всех простых чисел в диапазоне
# использование концепции сегментированного сита

from math import floor, sqrt

   

   
# Эта функция находит все простые числа меньше предела
# с использованием простого сита из эратосфена. Это магазины найдено
# простых чисел в списке простых []

def simpleSieve(limit, primes):

    mark = [False]*(limit+1)

      

    for i in range(2, limit+1):

        if not mark[i]:

            # Если еще не отмечено, то это простое

            primes.append(i)

            for j in range(i, limit+1, i):

                mark[j] = True

  

  
# Находит все простые числа в заданном диапазоне, используя
# сегментированное сито

def primesInRange(low, high):

      

    # Вычислить все простые числа, меньшие или равные

    # квадратный корень высокого с помощью простого сита

    limit = floor(sqrt(high)) + 1

    primes = list()

    simpleSieve(limit, primes)

  

    # Количество элементов в заданном диапазоне

    n = high - low + 1

      

    # Объявление булева только для [low, high]

    mark = [False]*(n+1)

  

    # Используйте найденные простые числа при помощи simpleSieve (), чтобы найти

    # простых чисел в заданном диапазоне

    for i in range(len(primes)):

        # Найдите минимальное число в [low..high], которое

        # кратное простому [i] (делится на простое [i])

        loLim = floor(low/primes[i]) * primes[i]

        if loLim < low:

            loLim += primes[i]

        if loLim == primes[i]:

            loLim += primes[i]

  

        # Пометить кратные простых чисел [i] в [low..high]:

        # Мы отмечаем j - низкий для j, то есть каждого числа

        # в диапазоне [низкий, высокий] отображается на [0, высокий-низкий]

        # поэтому, если диапазон [50, 100], маркировка 50 соответствует

        # маркировке 0, маркировка 51 соответствует 1 и

        # скоро. Таким образом, мы должны выделить место

        # только для диапазона

        for j in range(loLim, high+1, primes[i]):

            mark[j-low] = True

  

    # Числа, которые не отмечены в диапазоне, являются простыми

    for i in range(low, high+1):

        if not mark[i-low]:

            print(i, end = " ")

  

  

  
# Программа драйвера для проверки вышеуказанной функции

low = 10

high = 100

primesInRange(low, high)

Выход:

11  13  17  19  23  29  31  37  41  43  47  
53  59  61  67  71  73  79  83  89  97

Сегментированное сито (что если «высокое» значение диапазона слишком велико, а диапазон также велик)
Рассмотрим ситуацию, когда заданное высокое значение настолько велико, что ни sqrt (high), ни O (high-low + 1) не помещаются в памяти. Как найти примы в ассортименте. В этой ситуации мы запускаем шаг 1 (простое сито) только для предела, который может поместиться в памяти. Затем мы делим данный диапазон на разные сегменты. Для каждого сегмента мы выполняем шаги 2 и 3, рассматривая низкий и высокий как конечные точки текущего сегмента. Мы добавляем простые числа текущего сегмента к простому [] перед запуском следующего сегмента.

Эта статья предоставлена Уткаршем Триведи . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Сегментированное сито (печать простых чисел в диапазоне)

0.00 (0%) 0 votes