Рубрики

Сито Аткина

При заданном ограничении выведите все простые числа, меньшие или равные указанному пределу.

Примеры :

Input:  limit = 10
Output: 2, 3, 5, 7

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

Мы обсудили ниже алгоритмы для вышеуказанной задачи.
Сито Эратосфена
Сито Сундарама

Сито Аткина — это современный алгоритм поиска всех простых чисел вплоть до заданного целого числа. По сравнению с древним Ситом Эратосфена , который отмечает несколько простых чисел, он выполняет некоторую предварительную работу, а затем отмечает несколько квадратов простых чисел, поэтому он имеет лучшую теоретическую асимптотическую сложность со Сложностью (N / (log log N) )

Алгоритм:

  1. Создайте список результатов, заполненный 2, 3 и 5.
  2. Создайте список сит с записью для каждого положительного целого числа; Все записи в этом списке должны быть помечены как не простые.
  3. Для каждого номера записи n в списке сит по модулю шестьдесят остаток r:
    1. Если r равно 1, 13, 17, 29, 37, 41, 49 или 53, переверните запись для каждого возможного решения, чтобы 4x 2 + y 2 = n.
    2. Если r равно 7, 19, 31 или 43, измените запись для каждого возможного решения на 3x 2 + y 2 = n.
    3. Если r равно 11, 23, 47 или 59, измените запись для каждого возможного решения на 3x 2 — y 2 = n, когда x> y.
    4. Если r — что-то еще, полностью игнорируйте это ..
  4. Начните с самого низкого числа в списке сит.
  5. Возьмите следующий номер в списке сит, все еще отмеченный как простой.
  6. Включите номер в список результатов.
  7. Возведите в квадрат число и отметьте все кратные числа этого квадрата как не простые. Обратите внимание, что множители, которые могут быть учтены как 2, 3 или 5, не должны быть отмечены, так как они будут проигнорированы в окончательном перечислении простых чисел.
  8. Повторите шаги с четвертого по седьмой.

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

C ++

// C ++ программа для реализации Сита Аткина
#include <bits/stdc++.h>

using namespace std;

  

int SieveOfAtkin(int limit)

{

    // 2 и 3 известны как простые

    if (limit > 2)

        cout << 2 << " ";

    if (limit > 3)

        cout << 3 << " ";

  

    // Инициализируем массив сит с ложными значениями

    bool sieve[limit];

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

        sieve[i] = false;

  

    / * Mark siev [n] истинно, если один

       из следующего верно:

    а) n = (4 * x * x) + (y * y) имеет нечетное число

       решения, т. е. существуют

       нечетное количество различных пар (х, у)

       которые удовлетворяют уравнению и

        n% 12 = 1 или n% 12 = 5.

    б) n = (3 * x * x) + (y * y) имеет нечетное число

       растворов и n% 12 = 7

    c) n = (3 * x * x) - (y * y) имеет нечетное число

       растворы, x> y и n% 12 = 11 * /

    for (int x = 1; x * x < limit; x++) {

        for (int y = 1; y * y < limit; y++) {

              

            // Основная часть сита Аткина

            int n = (4 * x * x) + (y * y);

            if (n <= limit && (n % 12 == 1 || n % 12 == 5))

                sieve[n] ^= true;

  

            n = (3 * x * x) + (y * y);

            if (n <= limit && n % 12 == 7)

                sieve[n] ^= true;

  

            n = (3 * x * x) - (y * y);

            if (x > y && n <= limit && n % 12 == 11)

                sieve[n] ^= true;

        }

    }

  

    // Пометить все кратные квадраты как не простые

    for (int r = 5; r * r < limit; r++) {

        if (sieve[r]) {

            for (int i = r * r; i < limit; i += r * r)

                sieve[i] = false;

        }

    }

  

    // Печать простых чисел с помощью sieve []

    for (int a = 5; a < limit; a++)

        if (sieve[a])

            cout << a << " ";

}

  
// Драйвер программы

int main(void)

{

    int limit = 20;

    SieveOfAtkin(limit);

    return 0;

}

Джава

// Java-программа для реализации Sieve
// Аткина

class GFG {

  

    static int SieveOfAtkin(int limit)

    {

        // 2 и 3 известны как простые

        if (limit > 2)

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

  

        if (limit > 3)

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

  

        // Инициализируем массив сит с помощью

        // ложные значения

        boolean sieve[] = new boolean[limit];

  

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

            sieve[i] = false;

  

        / * Mark siev [n] верно, если один из

        следующее верно:

        а) n = (4 * x * x) + (y * y) имеет нечетное число

           решений, т. е. существуют

           нечетное количество различных пар

           (х, у), которые удовлетворяют уравнению

           и n% 12 = 1 или n% 12 = 5.

        б) n = (3 * x * x) + (y * y) имеет нечетное число

           растворов и п% 12 = 7

        c) n = (3 * x * x) - (y * y) имеет нечетное число

           растворов, x> y и n% 12 = 11 * /

        for (int x = 1; x * x < limit; x++) {

            for (int y = 1; y * y < limit; y++) {

  

                // Основная часть сита Аткина

                int n = (4 * x * x) + (y * y);

                if (n <= limit && (n % 12 == 1 || n % 12 == 5))

  

                    sieve[n] ^= true;

  

                n = (3 * x * x) + (y * y);

                if (n <= limit && n % 12 == 7)

                    sieve[n] ^= true;

  

                n = (3 * x * x) - (y * y);

                if (x > y && n <= limit && n % 12 == 11)

                    sieve[n] ^= true;

            }

        }

  

        // Пометить все кратные квадраты как

        // не простое

        for (int r = 5; r * r < limit; r++) {

            if (sieve[r]) {

                for (int i = r * r; i < limit;

                     i += r * r)

                    sieve[i] = false;

            }

        }

  

        // Печать простых чисел с помощью sieve []

        for (int a = 5; a < limit; a++)

            if (sieve[a])

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

        return 0;

    }

  

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

    public static void main(String[] args)

    {

        int limit = 20;

        SieveOfAtkin(limit);

    }

}

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

Python 3

# Python 3 программа для
# реализация
# Сито Аткина

  

def SieveOfAtkin(limit):

  

    № 2 и 3 известны

    # быть простым

    if (limit > 2):

        print(2 , end = " ")

    if (limit > 3):

        print(3 , end = " ")

  

    # Инициализировать сито

    # массив с ложными значениями

    sieve = [False] * limit

    for i in range( 0 , limit ):

        sieve[i] = False

          

    '' 'Mark siev [n] True, если

    верно одно из следующего:

    а) n = (4 * x * x) + (y * y) имеет нечетное

    количество решений, т. е.

    существует нечетное количество

    отдельные пары (х, у), которые

    удовлетворить уравнение и

    n% 12 = 1 или n% 12 = 5.

    б) n = (3 * x * x) + (y * y) имеет

    нечетное количество решений

    и n% 12 = 7

    c) n = (3 * x * x) - (y * y) имеет

    нечетное количество решений,

    x> y и n% 12 = 11 '' '

    x = 1

    while(x * x < limit ) :

        y = 1

        while(y * y < limit ) :

              

            # Основная часть

            # Сито Аткина

            n = (4 * x * x) + (y * y)

            if (n <= limit and (n % 12 == 1 or 

                                n % 12 == 5)):

                sieve[n] ^= True

  

            n = (3 * x * x) + (y * y)

            if (n <= limit and n % 12 == 7):

                sieve[n] ^= True

  

            n = (3 * x * x) - (y * y)

            if (x > y and n <= limit and 

                          n % 12 == 11):

                sieve[n] ^= True

            y += 1

        x += 1

      

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

    # квадраты как не простые

    r = 5

    while(r * r < limit) :

        if (sieve[r]) :

            for i in range(r * r, limit, r * r):

                sieve[i] = False

          

    # Печать простых чисел

    # используя сито []

    for a in range(5 , limit ):

        if (sieve[a]):

            print(a , end = " ")

  
Код водителя

limit = 20

SieveOfAtkin(limit)

  
# Этот код добавлен
# от Smitha

C #

// C # программа для реализации Sieve
// Аткина

using System;

  

class GFG {

  

    static int SieveOfAtkin(int limit)

    {

        // 2 и 3 известны как простые

        if (limit > 2)

            Console.Write(2 + " ");

  

        if (limit > 3)

            Console.Write(3 + " ");

  

        // Инициализируем массив сит с помощью

        // ложные значения

        bool[] sieve = new bool[limit];

  

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

            sieve[i] = false;

  

        / * Mark siev [n] верно, если один из

        следующее верно:

        а) n = (4 * x * x) + (y * y) имеет нечетное число

           решений, т. е. существуют

           нечетное количество различных пар

           (х, у), которые удовлетворяют уравнению

           и n% 12 = 1 или n% 12 = 5.

        б) n = (3 * x * x) + (y * y) имеет нечетное число

           растворов и п% 12 = 7

        c) n = (3 * x * x) - (y * y) имеет нечетное число

           растворов, x> y и n% 12 = 11 * /

        for (int x = 1; x * x < limit; x++) {

            for (int y = 1; y * y < limit; y++) {

  

                // Основная часть сита Аткина

                int n = (4 * x * x) + (y * y);

                if (n <= limit && (n % 12 == 1 || n % 12 == 5))

  

                    sieve[n] ^= true;

  

                n = (3 * x * x) + (y * y);

                if (n <= limit && n % 12 == 7)

                    sieve[n] ^= true;

  

                n = (3 * x * x) - (y * y);

                if (x > y && n <= limit && n % 12 == 11)

                    sieve[n] ^= true;

            }

        }

  

        // Пометить все кратные квадраты как

        // не простое

        for (int r = 5; r * r < limit; r++) {

            if (sieve[r]) {

                for (int i = r * r; i < limit;

                     i += r * r)

                    sieve[i] = false;

            }

        }

  

        // Печать простых чисел с помощью sieve []

        for (int a = 5; a < limit; a++)

            if (sieve[a])

                Console.Write(a + " ");

        return 0;

    }

  

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

    public static void Main()

    {

        int limit = 20;

        SieveOfAtkin(limit);

    }

}

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

PHP

<?php
// PHP программа для реализации
// Сита Аткина

  

function SieveOfAtkin($limit)

{

      

    // 2 и 3 известны

    // быть простым

    if ($limit > 2)

        echo 2 , " ";

    if ($limit > 3)

        echo 3 , " ";

  

    // Инициализируем ситовый массив

    // с ложными значениями

    $sieve[$limit] = 0;

    for ($i = 0; $i < $limit; $i++)

        $sieve[$i] = false;

  

    / * Mark siev [n] истинно, если один

       из следующего верно:

    а) n = (4 * x * x) + (y * y) имеет нечетное число

       решения, т. е. существуют

       нечетное количество различных пар (х, у)

       которые удовлетворяют уравнению и

       n% 12 = 1 или n% 12 = 5.

    б) n = (3 * x * x) + (y * y) имеет нечетное число

       растворов и n% 12 = 7

    c) n = (3 * x * x) - (y * y) имеет нечетное число

       растворы, x> y и n% 12 = 11 * /

    for ($x = 1; $x * $x < $limit; $x++)

    {

        for ($y = 1; $y * $y < $limit; $y++) 

        {

              

            // Основная часть сита Аткина

            $n = (4 * $x * $x) + ($y * $y);

            if ($n <= $limit && ($n % 12 == 1 || 

                                   $n % 12 == 5))

                $sieve[$n] ^= true;

  

            $n = (3 * $x * $x) + ($y * $y);

            if ($n <= $limit && $n % 12 == 7)

                $sieve[$n] = true;

  

            $n = (3 * $x * $x) - ($y * $y);

            if ($x > $y && $n <= $limit &&

                            $n % 12 == 11)

                $sieve[$n] ^= true;

        }

    }

  

    // Отметим все кратные

    // квадраты как не простые

    for ($r = 5; $r * $r < $limit; $r++) {

        if ($sieve[$r]) {

            for ($i = $r * $r; $i < $limit;

                             $i += $r * $r)

                $sieve[$i] = false;

        }

    }

  

    // Печать простых чисел

    // используя сито []

    for ($a = 5; $a < $limit; $a++)

        if ($sieve[$a])

            echo $a , " ";

}

  

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

    $limit = 20;

    SieveOfAtkin($limit);

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


Выход:

2 3 5 7 11 13 17 19 

Как это устроено:

  1. Алгоритм рассматривает 2, 3 и 5 как особые случаи и просто добавляет их к набору простых чисел для начала.
  2. Как и Sieve of Eratosthenes, мы начинаем со списка чисел, которые мы хотим исследовать. Предположим, что мы хотим найти простые числа <= 100, затем составим список для [5, 100]. Как объяснено в (1), 2, 3 и 5 являются частными случаями, а 4 не является простым.
  3. Алгоритм говорит в терминах остатков по модулю 60. ,
  4. Все числа с остатком по модулю шестьдесят 1, 13, 17, 29, 37, 41, 49 или 53 имеют остаток по модулю двенадцать от 1 или 5. Эти числа являются простыми тогда и только тогда, когда число решений 4 × 2 + y2 = n нечетно, а число не содержит квадратов. Целое число, свободное от квадрата, не делится ни на один идеальный квадрат, кроме 1.
  5. Все числа с остатком по модулю шестьдесят 7, 19, 31 или 43 имеют остаток по модулю шесть 1. Эти числа являются простыми тогда и только тогда, когда число решений 3x 2 + y 2 = n нечетно и число равно бесквадратным.
  6. Все числа с остатком по модулю шестьдесят 11, 23, 47 или 59 имеют остаток по модулю двенадцать из 11. Эти числа являются простыми в том и только в том случае, если число решений 3x 2 — y 2 = n нечетно и число равно бесквадратным.

Давайте посмотрим, как он генерирует простое число до 20:

1    2    3    4    5    6    7    8    9    10
11  12   13    14   15   16   17  18   19    20

Шаг 0:
Статус для всех чисел в начале является Ложным. Специальное число 2, 3 и 5, которые известны как простые.

Шаг 1:
Сгенерируйте значения для условий.

Шаг 2:
Листать статус в соответствии с условием.

Приведенные выше значения n в таблице, сгенерированной в цикле x, y, будут проверены на условие по модулю.
Столбец 1: if (значение colum1)% 12 == 1 или 5
затем переверните сито для этого номера.
Мы берем mod с 12 вместо 60, это потому, что если мы берем mod 60, то мы должны рассматривать многие r как 1, 13, 17, 29, 37, 41, 49 или 53 и для всех этих r, mod 12 — 1 или 5. (сделано только для уменьшения размера выражения)

Столбец 2: if (значение colum2)% 12 == 7
затем переверните сито для этого номера.

Столбец 3: if (значение colum3)% 12 == 11
затем переверните сито для этого номера.

Шаг 3 :
Проверка наличия квадрата бесплатно Условие: если в нашем списке есть любое число в квадрате любого числа, удалите его.

Шаг 4:
Создание массива простых чисел, для которых статус истинен.
т.е. 2 3 5 7 11 13 17 19

Шаг 5:
Распечатайте вывод на экране.

Источники:
https://en.wikipedia.org/wiki/Sieve_of_Atkin
http://primesieve.org/
http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf

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

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

Сито Аткина

0.00 (0%) 0 votes