Рубрики

Сито Эратосфена в 0 (n) временной сложности

Классический алгоритм Sieve of Eratosthenes занимает O (N log (log N)), чтобы найти все простые числа меньше N. В этой статье обсуждается модифицированное Sieve, которое работает за O (N).

Пример :

Given a number N, print all prime 
numbers smaller than N

Input :  int N = 15
Output : 2 3 5 7 11 13

Input : int N = 20
Output : 2 3 5 7 11 13 17 19

Алгоритм манипулированного сита Эратосфена работает следующим образом:

For every number i where i varies from 2 to N-1:
    Check if the number is prime. If the number
    is prime, store it in prime array.

For every prime numbers j less than or equal to the smallest  
prime factor p of i:
    Mark all numbers j*p as non_prime.
    Mark smallest prime factor of j*p as j

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

C ++

// C ++ программа для генерации всех простых чисел
// меньше чем N в O (N)
#include<bits/stdc++.h>

using namespace std;

const long long MAX_SIZE = 1000001;

  
// isPrime []: isPrime [i] равно true, если число простое
// prime []: сохраняет все простые числа меньше N
// SPF [], который хранит наименьший простой множитель числа
// [для Exp: наименьший простой фактор '8' и '16'
// равен 2, поэтому мы ставим SPF [8] = 2, SPF [16] = 2]

vector<long long >isprime(MAX_SIZE , true);

vector<long long >prime;

vector<long long >SPF(MAX_SIZE);

  
// функция генерирует все простые числа меньше чем N в O (n)

void manipulated_seive(int N)

{

    // 0 и 1 не простые

    isprime[0] = isprime[1] = false ;

  

    // Заполняем остальные записи

    for (long long int i=2; i<N ; i++)

    {

        // Если isPrime [i] == True, тогда i is

        // простое число

        if (isprime[i])

        {

            // помещаем i в простой [] вектор

            prime.push_back(i);

  

            // Простое число является его наименьшим

            // главный фактор

            SPF[i] = i;

        }

  

        // Удалить все кратные i * prime [j], которые

        // не простое, делая isPrime [i * prime [j]] = false

        // и положить наименьший простой множитель i * Prime [j] в качестве простого [j]

        // [для exp: let i = 5, j = 0, prime [j] = 2 [i * prime [j] = 10]

        // так что наименьший простой множитель '10' - это '2', который является простым [j]]

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

        for (long long int j=0;

             j < (int)prime.size() &&

             i*prime[j] < N && prime[j] <= SPF[i];

             j++)

        {

            isprime[i*prime[j]]=false;

  

            // положить наименьший простой множитель i * prime [j]

            SPF[i*prime[j]] = prime[j] ;

        }

    }

}

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

int main()

{

    int N = 13 ; // Должно быть меньше MAX_SIZE

  

    manipulated_seive(N);

  

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

    for (int i=0; i<prime.size() && prime[i] <= N ; i++)

        cout << prime[i] << " ";

  

    return 0;

}

Джава

// Java-программа для генерации всех простых чисел
// меньше чем N в O (N)

  

  

import java.util.Vector;

  

class Test

{

    static final int MAX_SIZE = 1000001;

    // isPrime []: isPrime [i] равно true, если число простое

    // prime []: сохраняет все простые числа меньше N

    // SPF [], который хранит наименьший простой множитель числа

    // [для Exp: наименьший простой фактор '8' и '16'

    // равен 2, поэтому мы ставим SPF [8] = 2, SPF [16] = 2]

    static Vector<Boolean>isprime = new Vector<>(MAX_SIZE);

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

    static Vector<Integer>SPF = new Vector<>(MAX_SIZE);

       

    // метод генерирует все простые числа меньше чем N в O (n)

    static void manipulated_seive(int N)

    {

        // 0 и 1 не простые

        isprime.set(0, false);

        isprime.set(1, false);

          

        // Заполняем остальные записи

        for (int i=2; i<N ; i++)

        {

            // Если isPrime [i] == True, тогда i is

            // простое число

            if (isprime.get(i))

            {

                // помещаем i в простой [] вектор

                prime.add(i);

       

                // Простое число является его наименьшим

                // главный фактор

                SPF.set(i,i);

            }

       

            // Удалить все кратные i * prime [j], которые

            // не простое, делая isPrime [i * prime [j]] = false

            // и положить наименьший простой множитель i * Prime [j] в качестве простого [j]

            // [для exp: let i = 5, j = 0, prime [j] = 2 [i * prime [j] = 10]

            // так что наименьший простой множитель '10' - это '2', который является простым [j]]

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

            for (int j=0;

                 j < prime.size() &&

                 i*prime.get(j) < N && prime.get(j) <= SPF.get(i);

                 j++)

            {

                isprime.set(i*prime.get(j),false);

       

                // положить наименьший простой множитель i * prime [j]

                SPF.set(i*prime.get(j),prime.get(j)) ;

            }

        }

    }

      

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

    public static void main(String args[]) 

    {

        int N = 13 ; // Должно быть меньше MAX_SIZE

          

        // инициализация isprime и spf

        for (int i = 0; i < MAX_SIZE; i++){

            isprime.add(true);

            SPF.add(2);

        }

  

          

        manipulated_seive(N);

       

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

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

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

    }

}

python3

# Python3 программа для генерации всего
# простые числа меньше N в O (N)

  

MAX_SIZE = 1000001

  
# isPrime []: isPrime [i] равно true, если
# число простое
# prime []: сохраняет все простые числа
# меньше чем N
# SPF [], которые хранят наименьшее простое число
# фактор числа [например, наименьший
# главный фактор «8» и «16»
# равно '2', поэтому мы ставим SPF [8] = 2,
# SPF [16] = 2]

isprime = [True] * MAX_SIZE 

prime = [] 

SPF = [None] * (MAX_SIZE) 

  
# функция генерирует все простые числа
# меньше чем N в O (n)

def manipulated_seive(N): 

  

    # 0 и 1 не простые

    isprime[0] = isprime[1] = False

  

    # Заполните остальные записи

    for i in range(2, N): 

      

        # Если isPrime [i] == True, тогда я

        # простое число

        if isprime[i] == True

          

            # поместите меня в простой вектор []

            prime.append(i) 

  

            # Простое число его наименьшее

            # главный фактор

            SPF[i] =

          

        # Удалить все кратные i * prime [j]

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

        # Prime [i * prime [j]] = ложь и положить

        # наименьший простой множитель i * Prime [j]

        # как простое число [j] [для exp: let i = 5, j = 0,

        # prime [j] = 2 [i * prime [j] = 10]

        # поэтому наименьшее простое множитель '10' равен '2'

        # это простое число [j]] этот цикл запускается только один

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

        j = 0

        while (j < len(prime) and

               i * prime[j] < N and

                   prime[j] <= SPF[i]):

          

            isprime[i * prime[j]] = False

  

            # положить наименьший простой множитель i * prime [j]

            SPF[i * prime[j]] = prime[j]

              

            j += 1

          
Код водителя

if __name__ == "__main__"

  

    N = 13 # Должно быть меньше MAX_SIZE

  

    manipulated_seive(N) 

  

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

    i = 0

    while i < len(prime) and prime[i] <= N:

        print(prime[i], end = " "

        i += 1

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

PHP

<?php
// PHP программа для генерации всего
// простые числа меньше N в O (N)

  

$MAX_SIZE = 10001;

  
// isPrime []: isPrime [i] равно true, если
// число простое
// prime []: сохраняет все простые числа
// меньше чем N
// SPF [], которые хранят наименьшее простое число
// коэффициент числа [например, наименьший
// главный фактор '8' и '16'
// равен 2, поэтому мы ставим SPF [8] = 2,
// SPF [16] = 2]

$isprime = array_fill(0, $MAX_SIZE, true); 

$prime = array(); 

$SPF = array_fill(0, $MAX_SIZE, 0); 

  
// функция генерирует все простые числа
// меньше чем N в O (n)

function manipulated_seive($N

{

    global $isprime, $MAX_SIZE,

                     $SPF, $prime;

      

    // 0 и 1 не простые

    $isprime[0] = $isprime[1] = false;

  

    // Заполняем остальные записи

    for ($i = 2; $i < $N; $i++)

    

      

        // Если isPrime [i] == True, то

        // я простое число

        if ($isprime[$i]) 

        {

          

            // помещаем i в простой [] вектор

            array_push($prime, $i); 

  

            // Простое число само по себе

            // наименьший простой фактор

            $SPF[$i] = $i;

        }

          

        // Удалить все кратные i * prime [j]

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

        // Prime [i * prime [j]] = false и положить

        // наименьший простой множитель i * Prime [j]

        // как простое число [j] [для exp: let i = 5, j = 0,

        // простое число [j] = 2 [i * простое число [j] = 10]

        // так что наименьший простой множитель '10' равен '2'

        // это простое число [j]] только этот цикл

        // один раз для числа, которое не простое

        $j = 0;

        while ($j < count($prime) &&

               $i * $prime[$j] < $N &&

               $prime[$j] <= $SPF[$i])

       {

            $isprime[$i * $prime[$j]] = false;

  

            // положить наименьший простой множитель i * prime [j]

            $SPF[$i * $prime[$j]] = $prime[$j];

              

            $j += 1;

        }

    }

}

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

$N = 13; // Должно быть меньше MAX_SIZE

  

manipulated_seive($N); 

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

$i = 0;

while ($i < count($prime) && 

       $prime[$i] <= $N)

{

    print($prime[$i] . " "); 

    $i += 1;

}

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


Выход :

2 3 5 7 11

Иллюстрация:

isPrime[0] = isPrime[1] = 0

After i = 2 iteration :
isPrime[]   [F, F, T, T, F, T, T, T] 
SPF[]       [0, 0, 2, 0, 2, 0, 0, 0]
     index   0  1  2  3  4  5  6  7

After i = 3 iteration :
isPrime[]  [F, F, T, T, F, T, F, T, T, F ]
SPF[]      [0, 0, 2, 3, 2, 0, 2, 0, 0, 3 ]
  index     0  1  2  3  4  5  6  7  8  9

After i = 4 iteration :
isPrime[]  [F, F, T, T, F, T, F, T, F, F]
SPF[]      [0, 0, 2, 3, 2, 0, 2, 0, 2, 3]
  index     0  1  2  3  4  5  6  7  8  9

Эта статья предоставлена Дивьяншу Шриваставой и Нишант Сингхом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Сито Эратосфена в 0 (n) временной сложности

0.00 (0%) 0 votes