Рубрики

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

Учитывая число n, выведите все простые числа меньше n. Например, если задано число 10, выведите 2, 3, 5, 7.

Наивный подход заключается в запуске цикла от 0 до n-1 и проверке каждого числа на простоту. Лучший подход — использовать простое сито Эратосфена .

// Эта функция находит все простые числа меньше, чем «limit»
// используя простое сито из эратосфена.

void simpleSieve(int limit)

{

    // Создаем логический массив "mark [0..limit-1]" и

    // инициализируем все записи как true. Ценность

    // в mark [p] будет, наконец, false, если 'p' не

    // простое число, иначе верно.

    bool mark[limit];

    memset(mark, true, sizeof(mark));

   

    // Один за другим пересекаем все числа так, чтобы их

    // кратные можно пометить как составные.

    for (int p=2; p*p<limit; p++)

    {

        // Если p не изменилось, то это простое число

        if (mark[p] == true)

        {

            // Обновить все кратные р

            for (int i=p*2; i<limit; i+=p)

                mark[i] = false;

        }

    }

   

    // Распечатать все простые числа и сохранить их в простом

    for (int p=2; p<limit; p++)

        if (mark[p] == true)

            cout << p << "  ";

}

Проблемы с простым ситом:
Сито Эратосфена выглядит хорошо, но, если учесть ситуацию, когда n большое, сито сталкивается со следующими проблемами.

  • Массив размером Θ (n) может не поместиться в памяти
  • Простое сито не подходит для кэширования даже для чуть большего размера. Алгоритм пересекает массив без местоположения ссылки

Сегментированное сито
Идея сегментированного сита состоит в том, чтобы разделить диапазон [0..n-1] на разные сегменты и вычислять простые числа во всех сегментах один за другим. Этот алгоритм сначала использует Simple Sieve, чтобы найти простые числа, меньшие или равные √ (n). Ниже приведены шаги, используемые в Сегментированном Сите.

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

В Simple Sieve нам требовалось пространство O (n), которое может оказаться невозможным для больших n. Здесь нам нужно пространство O (√n), и мы обрабатываем меньшие диапазоны за раз (местность ссылки)

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

C ++

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

using namespace std;

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

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

{

    // Создаем логический массив "mark [0..n-1]" и инициализируем

    // все записи этого как истина. Значение в отметке [p] будет

    // наконец, ложь, если 'p' не простое число, иначе true.

    bool mark[limit+1];

    memset(mark, true, sizeof(mark));

  

    for (int p=2; p*p<limit; p++)

    {

        // Если p не изменилось, то это простое число

        if (mark[p] == true)

        {

            // Обновить все кратные р

            for (int i=p*2; i<limit; i+=p)

                mark[i] = false;

        }

    }

  

    // Распечатать все простые числа и сохранить их в простом

    for (int p=2; p<limit; p++)

    {

        if (mark[p] == true)

        {

            prime.push_back(p);

            cout << p << " ";

        }

    }

}

  
// Печатает все простые числа меньше 'n'

void segmentedSieve(int n)

{

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

    // для получения квадратного корня из n с помощью простого сита

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

    vector<int> prime; 

    simpleSieve(limit, prime); 

  

    // Делим диапазон [0..n-1] на разные сегменты

    // Мы выбрали размер сегмента как sqrt (n).

    int low = limit;

    int high = 2*limit;

  

    // Пока все сегменты диапазона [0..n-1] не обработаны,

    // обрабатываем по одному сегменту за раз

    while (low < n)

    {

        if (high >= n) 

           high = n;

          

        // Чтобы отметить простые числа в текущем диапазоне. Значение в отметке [i]

        // в конечном итоге будет ложным, если i-low не простое число,

        // еще верно.

        bool mark[limit+1];

        memset(mark, true, sizeof(mark));

  

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

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

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

        {

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

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

            // Например, если low равен 31, а prime [i] равно 3,

            // мы начинаем с 33.

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

            if (loLim < low)

                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] = false;

        }

  

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

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

            if (mark[i - low] == true)

                cout << i << " ";

  

        // Обновление минимума и максимума для следующего сегмента

        low = low + limit;

        high = high + limit;

    }

}

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

int main()

{

    int n = 100;

    cout << "Primes smaller than " << n << ":n";

    segmentedSieve(n);

    return 0;

}

Джава

// Java-программа для печати распечатать все простые числа меньше
// n с использованием сегментированного сита

  

  

import java.util.Vector;

import static java.lang.Math.sqrt;

import static java.lang.Math.floor;

  

class Test

{

    // Этот метид находит все простые числа меньше «предела»

    // используя простое сито из эратосфена. Это также магазины

    // найдены простые числа в векторе prime []

    static void simpleSieve(int limit, Vector<Integer> prime)

    {

        // Создаем логический массив "mark [0..n-1]" и инициализируем

        // все записи этого как истина. Значение в отметке [p] будет

        // наконец, ложь, если 'p' не простое число, иначе true.

        boolean mark[] = new boolean[limit+1];

          

        for (int i = 0; i < mark.length; i++)

            mark[i] = true;

       

        for (int p=2; p*p<limit; p++)

        {

            // Если p не изменилось, то это простое число

            if (mark[p] == true)

            {

                // Обновить все кратные р

                for (int i=p*2; i<limit; i+=p)

                    mark[i] = false;

            }

        }

       

        // Распечатать все простые числа и сохранить их в простом

        for (int p=2; p<limit; p++)

        {

            if (mark[p] == true)

            {

                prime.add(p);

                System.out.print(p + "  ");

            }

        }

    }

       

    // Печатает все простые числа меньше 'n'

    static void segmentedSieve(int n)

    {

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

        // для получения квадратного корня из n с помощью простого сита

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

        Vector<Integer> prime = new Vector<>();  

        simpleSieve(limit, prime); 

       

        // Делим диапазон [0..n-1] на разные сегменты

        // Мы выбрали размер сегмента как sqrt (n).

        int low  = limit;

        int high = 2*limit;

       

        // Пока все сегменты диапазона [0..n-1] не обработаны,

        // обрабатываем по одному сегменту за раз

        while (low < n)

        {

            if (high >= n) 

                high = n;

  

            // Чтобы отметить простые числа в текущем диапазоне. Значение в отметке [i]

            // в конечном итоге будет ложным, если i-low не простое число,

            // еще верно.

            boolean mark[] = new boolean[limit+1];

              

            for (int i = 0; i < mark.length; i++)

                mark[i] = true;

       

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

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

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

            {

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

                // кратно prime.get (i) (делится на prime.get (i))

                // Например, если low равен 31, а prime.get (i) равен 3,

                // мы начинаем с 33.

                int loLim = (int) (floor(low/prime.get(i)) * prime.get(i));

                if (loLim < low)

                    loLim += prime.get(i);

       

                / * Пометить кратные значения prime.get (i) в [low..high]:

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

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

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

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

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

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

                for (int j=loLim; j<high; j+=prime.get(i))

                    mark[j-low] = false;

            }

       

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

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

                if (mark[i - low] == true)

                    System.out.print(i + "  ");

       

            // Обновление минимума и максимума для следующего сегмента

            low  = low + limit;

            high = high + limit;

        }

    }

      

    // Метод драйвера

    public static void main(String args[]) 

    {

        int n = 100;

        System.out.println("Primes smaller than " + n + ":");

        segmentedSieve(n);

    }

}

python3

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

import math

prime = []

  
# Этот метод находит все простые числа
# меньше, чем «предел», используя
# простое сито из эратосфена.
# Он также хранит найденные простые числа в списке простых чисел

def simpleSieve(limit):

      

    # Создайте логический список "mark [0..n-1]" и

    # инициализировать все записи как True.

    # Значение в отметке [p] будет, наконец, ложным

    # если 'p' не простое, иначе True.

    mark = [True for i in range(limit + 1)]

    p = 2

    while (p * p <= limit):

          

        # Если p не изменяется, то это простое число

        if (mark[p] == True): 

              

            # Обновить все кратные р

            for i in range(p * p, limit + 1, p): 

                mark[i] = False  

        p += 1

          

    # Распечатать все простые числа

    # и хранить их в простом

    for p in range(2, limit): 

        if mark[p]:

            prime.append(p)

            print(p,end = " ")

              
# Печатает все простые числа меньше 'n'

def segmentedSieve(n):

      

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

    # до квадратного корня из n с помощью простого сита

    limit = int(math.floor(math.sqrt(n)) + 1)

    simpleSieve(limit)

      

    # Разделите диапазон [0..n-1] на разные сегменты

    # Мы выбрали размер сегмента как sqrt (n).

    low = limit

    high = limit * 2

      

    # Пока все сегменты диапазона [0..n-1] не обработаны,

    # обрабатывать один сегмент за раз

    while low < n:

        if high >= n:

            high = n

              

        # Чтобы отметить простые числа в текущем диапазоне. Значение в отметке [i]

        # в конце концов будет False, если i-low не простое число,

        # еще верно.

        mark = [True for i in range(limit + 1)]

          

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

        # найти простые числа в текущем диапазоне

        for i in range(len(prime)):

              

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

            # это кратное простого [i]

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

            # Например, если низкий - 31, а простое [i] - 3,

            # мы начинаем с 33.

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

                                         prime[i])

            if loLim < low:

                loLim += prime[i]

                  

            # Отметить кратные простого [i] в [low..high]:

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

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

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

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

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

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

            for j in range(loLim, high, prime[i]):

                mark[j - low] = False

                  

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

        for i in range(low, high):

            if mark[i - low]:

                print(i, end = " ")

                  

        # Обновление минимума и максимума для следующего сегмента

        low = low + limit

        high = high + limit

  
Код водителя

n = 100

print("Primes smaller than", n, ":")

segmentedSieve(100)

  
# Этот код предоставлен bhavyadeep

C #

// C # программа для печати на печать
// все простые числа меньше чем
// n с использованием сегментированного сита

using System;

using System.Collections;

  

class GFG

{

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

    // меньше, чем 'limit', используя простой

    // сито из эратосфена. Это также магазины

    // найдены простые числа в векторе prime []

    static void simpleSieve(int limit,

                            ArrayList prime)

    {

        // Создаем логический массив "mark [0..n-1]"

        // и инициализируем все записи как

        // правда. Значение в метке [p] будет, наконец,

        // false, если 'p' не простое, иначе true.

        bool[] mark = new bool[limit + 1];

          

        for (int i = 0; i < mark.Length; i++)

            mark[i] = true;

      

        for (int p = 2; p * p < limit; p++)

        {

            // Если p не изменилось, то это простое число

            if (mark[p] == true)

            {

                // Обновить все кратные р

                for (int i = p * 2; i < limit; i += p)

                    mark[i] = false;

            }

        }

      

        // Распечатать все простые числа и сохранить их в простом

        for (int p = 2; p < limit; p++)

        {

            if (mark[p] == true)

            {

                prime.Add(p);

                Console.Write(p + " ");

            }

        }

    }

      

    // Печатает все простые числа меньше 'n'

    static void segmentedSieve(int n)

    {

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

        // для получения квадратного корня из n с помощью простого сита

        int limit = (int) (Math.Floor(Math.Sqrt(n)) + 1);

        ArrayList prime = new ArrayList(); 

        simpleSieve(limit, prime); 

      

        // Делим диапазон [0..n-1] на

        // разные сегменты мы выбрали

        // размер сегмента как sqrt (n).

        int low = limit;

        int high = 2*limit;

      

        // Пока все сегменты диапазона

        // [0..n-1] не обрабатываются,

        // обрабатываем по одному сегменту за раз

        while (low < n)

        {

            if (high >= n) 

                high = n;

  

            // Чтобы отметить простые числа в текущем диапазоне.

            // Значение в mark [i] будет окончательно

            // быть ложным, если 'i-low' не простое число,

            // еще верно.

            bool[] mark = new bool[limit + 1];

              

            for (int i = 0; i < mark.Length; i++)

                mark[i] = true;

      

            // Используем найденные простые числа

            // simpleSieve () для поиска

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

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

            {

                // Находим минимальное число в

                // [low..high], который является кратным

                // из prime.get (i) (делится на

                // prime.get (i)) Например,

                // если низкий 31 и prime.get (i)

                // равно 3, мы начинаем с 33.

                int loLim = ((int)Math.Floor((double)(low / 

                            (int)prime[i])) * (int)prime[i]);

                if (loLim < low)

                    loLim += (int)prime[i];

      

                / * Пометить кратные значения prime.get (i) в [low..high]:

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

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

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

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

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

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

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

                    mark[j-low] = false;

            }

      

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

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

                if (mark[i - low] == true)

                    Console.Write(i + " ");

      

            // Обновление минимума и максимума для следующего сегмента

            low = low + limit;

            high = high + limit;

        }

    }

      

    // Код драйвера

    static void Main() 

    {

        int n = 100;

        Console.WriteLine("Primes smaller than " + n + ":");

        segmentedSieve(n);

    }

}

  
// Этот код предоставлен mits


Выход:

Primes smaller than 100:
2 3 5 7 11 13 17 19 23 29 31 37 41
43 47 53 59 61 67 71 73 79 83 89 97  

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

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

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

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

0.00 (0%) 0 votes