Рубрики

Сито Эратосфена

Учитывая число n, выведите все простые числа, меньшие или равные n. Также дано, что n — небольшое число.

Пример:

Input : n =10
Output : 2 3 5 7 

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

Сито Эратосфена является одним из наиболее эффективных способов найти все простые числа, меньшие n, когда n меньше 10 миллионов или около того (Ref Wiki ).

Ниже приведен алгоритм нахождения всех простых чисел, меньших или равных данному целому числу n по методу Эратосфена:

  1. Создайте список последовательных целых чисел от 2 до n : (2, 3, 4,…, n ).
  2. Первоначально, пусть p равно 2, первое простое число.
  3. Начиная с p 2 , посчитайте с шагом p и отметьте каждое из этих чисел, большее или равное p 2 , в списке. Эти числа будут p (p + 1) , p (p + 2) , p (p + 3) и т. Д.
  4. Найдите первое число больше p в списке, который не отмечен. Если такого номера не было, остановитесь. В противном случае, пусть теперь p равно этому числу (которое является следующим простым числом), и повторите процедуру с шага 3.

Когда алгоритм завершается, все числа в списке, которые не отмечены, являются простыми.

Объяснение с примером:
Давайте возьмем пример, когда n = 50. Таким образом, мы должны напечатать все числа печати, меньшие или равные 50.

Создаем список всех чисел от 2 до 50.

В соответствии с алгоритмом мы будем отмечать все числа, которые делятся на 2 и больше или равны его квадрату.

Теперь мы переходим к нашему следующему неотмеченному номеру 3 и отмечаем все числа, которые кратны 3 и больше или равны его квадрату.

Мы переходим к нашему следующему неотмеченному номеру 5 и отмечаем все кратные 5 и больше или равны его квадрату.

Мы продолжаем этот процесс, и наш финальный стол будет выглядеть следующим образом:

Итак, простыми числами являются безымянные: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Спасибо Кришан Кумар за предоставленное объяснение.


Реализация:

Ниже приведена реализация вышеуказанного алгоритма. В следующей реализации для обозначения кратных простых чисел используется логический массив arr [] размера n.

C / C ++

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

using namespace std;

  

void SieveOfEratosthenes(int n)

{

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

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

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

    bool prime[n+1];

    memset(prime, true, sizeof(prime));

  

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

    {

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

        if (prime[p] == true)

        {

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

            // равно квадрату этого

            // числа, кратные p и

            // меньше p ^ 2 уже помечены.

            for (int i=p*p; i<=n; i += p)

                prime[i] = false;

        }

    }

  

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

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

       if (prime[p])

          cout << p << " ";

}

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

int main()

{

    int n = 30;

    cout << "Following are the prime numbers smaller "

         << " than or equal to " << n << endl;

    SieveOfEratosthenes(n);

    return 0;

}

Джава

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

  

class SieveOfEratosthenes

{

    void sieveOfEratosthenes(int n)

    {

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

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

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

        boolean prime[] = new boolean[n+1];

        for(int i=0;i<n;i++)

            prime[i] = true;

          

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

        {

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

            if(prime[p] == true)

            {

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

                for(int i = p*p; i <= n; i += p)

                    prime[i] = false;

            }

        }

          

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

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

        {

            if(prime[i] == true)

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

        }

    }

      

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

    public static void main(String args[])

    {

        int n = 30;

        System.out.print("Following are the prime numbers ");

        System.out.println("smaller than or equal to " + n);

        SieveOfEratosthenes g = new SieveOfEratosthenes();

        g.sieveOfEratosthenes(n);

    }

}

  
// Этот код предоставлен Амитом Хандельвалом.

питон

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

  

def SieveOfEratosthenes(n):

      

    # Создайте логический массив "prime [0..n]" и инициализируйте

    # все записи это как правда. Значение в простом [i] будет

    # в конечном итоге быть ложным, если я не простое число, иначе верно.

    prime = [True for i in range(n+1)]

    p = 2

    while (p * p <= n):

          

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

        if (prime[p] == True):

              

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

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

                prime[i] = False

        p += 1

      

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

    for p in range(2, n):

        if prime[p]:

            print p,

  
# драйверная программа

if __name__=='__main__':

    n = 30

    print "Following are the prime numbers smaller",

    print "than or equal to", n

    SieveOfEratosthenes(n)

C #

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

using System;

  

namespace prime

{

    public class GFG

    {     

                  

        public static void SieveOfEratosthenes(int n)

        {

              

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

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

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

  

        bool[] prime = new bool[n+1];

          

        for(int i = 0; i < n; i++)

            prime[i] = true;

          

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

        {

            // Если штрих [p] не изменился,

            // тогда это простое число

            if(prime[p] == true)

            {

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

                for(int i = p*p; i <= n; i += p)

                    prime[i] = false;

            }

        }

          

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

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

        {

            if(prime[i] == true)

                Console.Write(i + " ");

        }

              

        }

          

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

        public static void Main()

        {

            int n = 30;

            Console.WriteLine("Following are the prime numbers");

            Console.WriteLine("smaller than or equal to " + n);

            SieveOfEratosthenes(n);

              

        }

    }

}

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

PHP

<?php
// PHP программа для печати всех простых чисел меньше
// чем или равно n, используя Sieve of
// Эратосфен

  

function SieveOfEratosthenes($n)

{

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

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

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

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

    $prime = array_fill(0, $n+1, true);

  

    for ($p = 2; $p*$p <= $n; $p++)

    {

          

        // Если штрих [p] не изменился,

        // тогда это простое число

        if ($prime[$p] == true)

        {

              

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

            for ($i = $p*$p; $i <= $n; $i += $p)

                $prime[$i] = false;

        }

    }

  

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

    for ($p = 2; $p <= $n; $p++)

        if ($prime[$p])

            echo $p." ";

}

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

    $n = 30;

    echo "Following are the prime numbers "

     ."smaller than or equal to " .$n."\n" ;

    SieveOfEratosthenes($n);

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


Выход:

Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29

Временная сложность: O (n * log (log (n)))

Вы также можете увидеть:
Сегментированное сито .
Сито Эратосфена в 0 (n) временной сложности

Ссылки:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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

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

Сито Эратосфена

0.00 (0%) 0 votes