Как найти следующее простое число алгоритм

Как найти следующее простое число алгоритм

Алгоритмы поиска простых чисел

Время на прочтение
6 мин

Количество просмотров 134K

«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.

Решето Эратосфена

Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно

$leqslant sqrt{n}$, алгоритм можно останавливать, после вычеркивания чисел делящихся на

$sqrt{n}$.

Иллюстрация работы алгоритма из Википедии:

image

Сложность алгоритма составляет

$O(n loglog n)$, при этом, для хранения информации о том, какие числа были вычеркнуты требуется

$O(n)$ памяти.

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до

$sqrt{log n}$. Это позволяет снизить сложность алгоритма в

$loglog n$ раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером

$leqslant sqrt{n}$ и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до

$O(sqrt{n})$.

Решето Аткина

Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина. Этот способ основан на следующих трех свойствах простых чисел.

Свойство 1

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 1(mod 4)$. То n — простое, тогда и только тогда, когда число корней уравнения

$4x^2+y^2=n$ нечетно.

Свойство 2

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 1(mod 6)$. То n — простое, тогда и только тогда, когда число корней уравнения

$3x^2+y^2=n$ нечетно.

Свойство 3

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 11(mod 12)$. То n — простое, тогда и только тогда, когда число корней уравнения

$3x^2-y^2=n$ нечетно.

Доказательства этих свойств приводятся в этой статье.

На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все

$x, y < sqrt n$. Для каждой такой пары вычисляется

$4x^2+y^2$,

$3x^2+y^2$,

$3x^2-y^2$ и значение элементов массива

$A[4x^2+y^2]$,

$A[3x^2+y^2]$,

$A[3x^2-y^2]$ увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют

$O(n)$. При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до

$O(n / loglog n)$, а потребление памяти до

$O(sqrt{n})$.

Числа Мерсенна и тест Люка-Лемера

Конечно при таких показателях сложности, даже оптимизированное решето Аткина невозможно использовать для поиска по-настоящему больших простых чисел. К счастью, существуют быстрые тесты, позволяющие проверить является ли заданное число простым. В отличие от алгоритмов решета, такие тесты не предназначены для поиска всех простых чисел, они лишь способны сказать с некоторой вероятностью, является ли определенное число простым.

Один из таких методов проверки — тест Люка-Лемера. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида

$2^p-1$, где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна

$M_p=2^p-1$ простое тогда и только тогда, когда p — простое и

$M_p$ делит нацело

$(p-1)$-й член последовательности

$S_k$ задаваемой рекуррентно:

$S_1=4, S_k=S_{k-1}^2-2$ для

$k > 1$.

Для числа

$M_p$ длиной p бит вычислительная сложность алгоритма составляет

${displaystyle O(p^{3})}$.

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня —

$2^{82,589,933}-1$, его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.

Теорема Ферма и тест Миллера-Рабина

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство

$a^{n-1}equiv 1{pmod {n}}$. Доказательство теоремы можно найти на Википедии.

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство

$a^{n-1} notequiv 1 pmod n$, то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение

$a^{n-1}equiv 1{pmod {n}}$ выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

Тест Миллера-Рабина

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения

$x^2 equiv 1 pmod p$, кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и

$p-1=2^sd$, тогда для любого a справедливо хотя бы одно из условий:

  1. $a^{d}equiv pm1{pmod {p}}$
  2. Существует целое число r < s такое, что $a^{2^{r}d}equiv -1{pmod {p}}$

По теореме Ферма

$a^{p-1}equiv1pmod p$, а так как

$p-1=2^sd$ из свойства о корнях уравнения

$x^2 equiv 1 pmod p$ следует что если мы найдем такое a, для которого одно из условий не выполняется, значит p — составное число. Если одно из условий выполняется, число a называют свидетелем простоты числа n по Миллеру, а само число n — вероятно простым.

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно

$1/4$.

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое

$approx(1/4)^k$.

Сложность работы алгоритма

$O(klog^3p)$, где k — количество проверок.

Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе , этого не всегда оказывается достаточно.

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили все числа до

$2^{64}$ и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше

$2^{64}$ тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.

Тест Люка на сильную псевдопростоту

Последовательности Люка — пары рекуррентных последовательностей

${U_{n}(P,Q)}, {V_{n}(P,Q)}$, описываемые выражениями:

${displaystyle U_{0}(P,Q)=0,quad U_{1}(P,Q)=1,quad U_{n+2}(P,Q)=Pcdot U_{n+1}(P,Q)-Qcdot U_{n}(P,Q),,ngeq 0}$

${displaystyle V_{0}(P,Q)=2,quad V_{1}(P,Q)=P,quad V_{n+2}(P,Q)=Pcdot V_{n+1}(P,Q)-Qcdot V_{n}(P,Q),,ngeq 0}$

Пусть

$U_n(P,Q)$ и

$V_n(P,Q)$ — последовательности Люка, где целые числа P и Q удовлетворяют условию

${displaystyle D=P^{2}-4Qneq 0}$

Вычислим символ Якоби:

$left({frac {D}{p}}right)=varepsilon$.

Найдем такие r, s для которых выполняется равенство

$n-ε=2^rs$

Для простого числа n выполняется одно из следующих условий:

  1. n делит $U_s$
  2. n делит $V_{2^js}$ для некоторого j < r

В противном случае n — составное.

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет

$(4/15)^k$.

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

Заключение

В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до

$10^8$. Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется

$M_p=2^p-1$.

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен

${frac {1}{ln n}}$. Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

P.S. Исходники

Реализацию всех описанных алгоритмов на Go можно посмотреть на GitHub.

Источник

How can I find the least prime number greater than a given number? For example, given 4, I need 5; given 7, I need 11.

I would like to know some ideas on best algorithms to do this. One method that I thought of was generate primes numbers through the Sieve of Eratosthenes, and then find the prime after the given number.

Jon Seigel's user avatar

Jon Seigel

12.2k8 gold badges57 silver badges92 bronze badges

asked Mar 18, 2010 at 8:44

avd's user avatar

0

Source: Wikipedia

Bertrand’s postulate (actually a theorem) states that if n > 3 is an integer, then there always exists at least one prime number p with n < p < 2n − 2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2n.

So if I am given a number, say n, than I can check in the range (n, 2*n) [open interval excluding n and 2*n]

int GetNextPrime(int n)
{
    bool isPrime = false;
    for (int i = n; i < 2 * n; ++i)
    {
    // go with your regular prime checking routine
    // as soon as you find a prime, break this for loop
    }
}

John R Perry's user avatar

John R Perry

3,8962 gold badges38 silver badges62 bronze badges

answered Mar 18, 2010 at 20:36

Rajendra Uppal's user avatar

Rajendra UppalRajendra Uppal

18.9k15 gold badges59 silver badges57 bronze badges

3

Some other methods have been suggested and I think that they are good, but it really depends on how much you want to have to store or compute on the spot. For instance if you are looking for the next prime after a very large number, then using the Sieve of Eratosthenes might not be so great because of the number of bits you would need to store.

Alternatively, you could check all odd integers between (and including) 3 and sqrt(N) on every number odd number N greater than the input number until you find the correct number. Of course you can stop checking when you find it is composite.

If you want a different method, then I would suggest using the Miller-Rabin primality test on all odd numbers above the input number (assuming the input is > 1) until a prime is found. If you follow the list, located at the bottom of the page, of numbers a to check for the given ranges, you can significantly cut down on the number of as you need to check. Of course, you might want to check at least a few of the smaller primes (3,5,7,11 for instance) before checking with Miller-Rabin.

answered Mar 19, 2010 at 5:58

Justin Peel's user avatar

Justin PeelJustin Peel

46.6k6 gold badges58 silver badges80 bronze badges

I have done this before.

Only addition is Bertrand’s Theorem from Rajendra’s Answer.

And readymade code from topcoder.

#include<iostream>
using namespace std;

/* This function calculates (ab)%c */
int modulo(int a,int b,int c){
    long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}

/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

int main(int argc, char* argv[])
{

    int input = 1000;
    int i = 0;

    if(input%2==0)
        i = input+1;
    else i = input;

    for(;i<2*input;i+=2) // from Rajendra's answer
        if(Miller(i,20)) // 18-20 iterations are enough for most of the applications.
            break;
    cout<<i<<endl;

    return 0;
}

Community's user avatar

answered Mar 20, 2010 at 21:25

Pratik Deoghare's user avatar

Pratik DeogharePratik Deoghare

35.1k30 gold badges100 silver badges146 bronze badges

I generally see two ways to do that.

  • counting up from n and checking every number for it being prime or not
  • generate prime numbers and check against them. (maybe do that beforehand, use an existing primenumber table, so you don’t need to calculate stuff everytime (well as long as N is within the range of your pre-calculated table)

maybe this helps too, (simply replace 2 with your given Number and N with infinite 😀 )
finding all prime numbers between 2 and N

N 1.1's user avatar

N 1.1

12.4k6 gold badges43 silver badges61 bronze badges

answered Mar 18, 2010 at 8:54

samsam's user avatar

samsamsamsam

3,15024 silver badges40 bronze badges

I’d have a big lookup table and then search it for the given number and respond with the next in the sequence.

Works well if there is a known (sensible) upper limit on the range of given numbers.

answered Mar 18, 2010 at 8:53

Martin's user avatar

MartinMartin

39.3k20 gold badges98 silver badges130 bronze badges

2

        int length = number;
        bool flag = true;
        for (int i = number; i <= length; i++)
        {
            for (int k = 2; k < length; k++)
            {
                if (i != k && i % k == 0)
                {
                    flag = false;
                    length = length + 1;
                    break;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
            flag = true;
        }

answered Feb 26, 2021 at 3:29

Abhay's user avatar

1

import java.util.Scanner;

public class Practice11 {

public static void main(String[] args) 
{
    int count=0;
    Scanner scan=new Scanner(System.in);
    System.out.println("enter a number:");
    int a=scan.nextInt();
    
   a: for(int i=a+1;i<a+1000;i++)// a+1000 because it will check up to 
                                //that number to find the next prime 
    {
        count=0;
        for(int j=2;j<i;j++)
        {
            if(i%j==0) //this will check if a number is divisible by another 
                       // number
            {
            count++;
            }
            else
            {
            }
           }
        if(count==0)
        {
            System.out.println(i);
            break a;//this line will break the loop so you get only one prime 
                      //number 
        }
    }

}

}

answered Jan 18, 2022 at 15:05

anuj kumar's user avatar

private static int nextPrime(int num) {
        num++;
        for (int i = 2; i <num; i++) {
            if(num%i == 0) {
                num++;
                i=2;
            } else{
                continue;
            }
        }
        return num;
    }

answered May 18, 2017 at 19:07

ranafeb14's user avatar

ranafeb14ranafeb14

4371 gold badge7 silver badges12 bronze badges

1

Источник

Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.

Теория чисел

  • Простые числа
  • Разложение на простые множители
  • Решето Эратосфена
  • Линейное решето Эратосфена*
  • НОД и НОК
  • Алгоритм Евклида
  • Расширенный алгоритм Евклида*
  • Операции по модулю
  • Быстрое возведение в степень
  • Деление по простому модулю*

Простые числа

Простым называется натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается. Составным числом называют непростое число, которое еще и не единица.

Примеры простых чисел: (2), (3), (5), (179), (10^9+7), (10^9+9).

Примеры составных чисел: (4), (15), (2^{30}).

Еще одно определение простого числа: (N) — простое, если у (N) ровно два делителя. Эти делители при этом равны (1) и (N).

Проверка на простоту за линию

С точки зрения программирования интересно научиться проверять, является ли число (N) простым. Это очень легко сделать за (O(N)) – нужно просто проверить, делится ли оно хотя бы на одно из чисел (2, 3, 4, ldots, N-1) . (N > 1) является простым только в случае, если оно не делится на на одно из этих чисел.

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, n): # начинаем с 2, так как на 1 все делится; n не включается
        if n % i == 0:
            return False
    return True

for i in range(1, 10):
    print(i, is_prime(i))
(1, False)
(2, True)
(3, True)
(4, False)
(5, True)
(6, False)
(7, True)
(8, False)
(9, False)

Проверка на простоту за корень

Алгоритм можно ускорить с (O(N)) до (O(sqrt{N})).

Пусть (N = a times b), причем (a leq b). Тогда заметим, что (a leq sqrt N leq b).

Почему? Потому что если (a leq b < sqrt{N}), то (ab leq b^2 < N), но (ab = N). А если (sqrt{N} < a leq b), то (N < a^2 leq ab), но (ab = N).

Иными словами, если число (N) равно произведению двух других, то одно из них не больше корня из (N), а другое не меньше корня из (N).

Из этого следует, что если число (N) не делится ни на одно из чисел (2, 3, 4, ldots, lfloorsqrt{N}rfloor), то оно не делится и ни на одно из чисел (lceilsqrt{N}rceil + 1, ldots, N-2, N-1), так как если есть делитель больше корня (не равный (N)), то есть делитель и меньше корня (не равный 1). Поэтому в цикле for достаточно проверять числа не до (N), а до корня.

def is_prime(n):
    if n == 1:
        return False
    # Удобно вместо for i in range(2, n ** 0.5) писать так:
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

for i in [1, 2, 3, 10, 11, 12, 10**9+6, 10**9+7]:
    print(i, is_prime(i))
(1, False)
(2, True)
(3, True)
(10, False)
(11, True)
(12, False)
(1000000006, False)
(1000000007, True)

Разложение на простые множители

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

[11 = 11 = 11^1] [100 = 2 times 2 times 5 times 5 = 2^2 times 5^2] [126 = 2 times 3 times 3 times 7 = 2^1 times 3^2 times 7^1]

Рассмотрим, например, такую задачу:

Условие: Нужно разбить (N) людей на группы равного размера. Нам интересно, какие размеры это могут быть.

Решение: По сути нас просят найти число делителей (N). Нужно посмотреть на разложение числа (N) на простые множители, в общем виде оно выглядит так:

[N= p_1^{a_1} times p_2^{a_2} times ldots times p_k^{a_k}]

Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень (i)-го простого число от 0 до (a_i) (то есть (a_i+1) различное значение), и так для каждого. То есть делитель (N) выглядит ровно так: [M= p_1^{b_1} times p_2^{b_2} times ldots times p_k^{b_k}, 0 leq b_i leq a_i] Значит, ответом будет произведение ((a_1+1) times (a_2+1) times ldots times (a_k + 1)).

Алгоритм разложения на простые множители

Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа (N), мы можем число (N) на него поделить и продолжить искать новый минимальный простой делитель.

Будем перебирать простой делитель от (2) до корня из (N) (как и раньше), но в случае, если (N) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ((N) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда (N) стало либо (1), либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само (N) добавить в ответ.

Напишем алгоритм факторизации:

def factorize(n):
    factors = []
    i = 2
    while i * i <= n: # перебираем простой делитель
        while n % i == 0: # пока N на него делится
            n //= i # делим N на этот делитель
            factors.append(i)
        i += 1
    # возможно, в конце N стало большим простым числом,
    # у которого мы дошли до корня и поняли, что оно простое
    # его тоже нужно добавить в разложение
    if n > 1:
        factors.append(n)
    return factors

for i in [1, 2, 3, 10, 11, 12, 10**9+6, 10**9+7]:
    print(i, '=', ' x '.join(str(x) for x in factorize(i)))
1 = 
2 = 2
3 = 3
10 = 2 x 5
11 = 11
12 = 2 x 2 x 3
1000000006 = 2 x 500000003
1000000007 = 1000000007

Задание

За сколько работает этот алгоритм?

.

.

.

.

Решение

За те же самые (O(sqrt{N})). Итераций цикла while с перебором делителя будет не больше, чем (sqrt{N}). Причем ровно (sqrt{N}) операций будет только в том случае, если (N) – простое.

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

Задание

Докажите, что число (N) имеет не больше, чем (O(log{N})) простых множителей в факторизации.

Разные свойства простых чисел*

Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:

  • Простых чисел, меньших (N), примерно (frac{N}{ln N}).
  • N-ое простое число равно примерно (Nln N).
  • Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
  • Для любого (N ge 2) на интервале ((N, 2N)) всегда найдется простое число (Постулат Бертрана)
  • Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить – это начать с (N! + 2).
  • Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
  • Максимальное число делителей равно примерно (O(sqrt[3]{n})). Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
  • Максимальное число делителей у числа на отрезке ([1, 10^5]) — 128
  • Максимальное число делителей у числа на отрекзке ([1, 10^9]) — 1344
  • Максимальное число делителей у числа на отрезке ([1, 10^{18}]) — 103680
  • Наука умеет факторизовать числа за (O(sqrt[4]{n})), но об этом как-нибудь в другой раз.
  • Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.

Решето Эратосфена

Часто нужно не проверять на простоту одно число, а найти все простые числа до (N). В этом случае наивный алгоритм будет работать за (O(Nsqrt N)), так как нужно проверить на простоту каждое число от 1 до (N).

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до (N) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Красивая визуализация

Задание

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

N = 50
prime = [1] * (N + 1)
prime[0], prime[1] = 0, 0
for i in range(2, N + 1): # можно и до sqrt(N)
    if prime[i]:
        for j in range(2 * i, N + 1, i): # идем с шагом i, можно начиная с i * i
            prime[j] = 0
for i in range(1, N + 1):
    if prime[i]:
        print(i)
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

У этого алгоритма можно сразу заметить несколько ускорений.

Во-первых, число (i) имеет смысл перебирать только до корня из (N), потому что при зачеркивании составных чисел, делящихся на простое (i > sqrt N), мы ничего не зачеркнем. Почему? Пусть существует составное (M leq N), которое делится на %i%, и мы его не зачеркнули. Но тогда (i > sqrt N geq sqrt M), а значит по ранее нами доказанному утверждению (M) должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.

Во-вторых, по этой же самое причине (j) имеет смысл перебирать только начиная с (i^2). Зачем вычеркивать (2i), (3i), (4i), …, ((i-1)i), если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на (2), (3), (4), …, ((i-1)).

Асимптотика

Такой код будет работать за (O(N log log N)) по причинам, которые мы пока не хотим объяснять формально.

Гармонический ряд

Научимся оценивать асимптотику величины (1 + frac{1}{2} + ldots + frac{1}{N}), которая нередко встречается в задачах, где фигурирует делимость.

Возьмем (N) равное (2^i – 1) и запишем нашу сумму следующим образом: [left(frac{1}{1}right) + left(frac{1}{2} + frac{1}{3}right) + left(frac{1}{4} + ldots + frac{1}{7}right) + ldots + left(frac{1}{2^{i – 1}} + ldots + frac{1}{2^i – 1}right)]

Каждое из этих слагаемых имеет вид [frac{1}{2^j} + ldots + frac{1}{2^{j + 1} – 1} le frac{1}{2^j} + ldots + frac{1}{2^j} = 2^j frac{1}{2^j} = 1]

Таким образом, наша сумма не превосходит (1 + 1 + ldots + 1 = i le 2log_2(2^i – 1)). Тем самым, взяв любое (N) и дополнив до степени двойки, мы получили асимптотику (O(log N)).

Оценку снизу можно получить аналогичным образом, оценив каждое такое слагаемое снизу значением (frac{1}{2}).

Попытка объяснения асимптотики** (для старших классов)

Мы знаем, что гармонический ряд (1 + frac{1}{2} + frac{1}{3} + ldots + frac{1}{N}) это примерно (log N), а значит [N + frac{N}{2} + frac{N}{3} + ldots + frac{N}{N} sim N log N]

А что такое асимптотика решета Эратосфена? Мы как раз ровно (frac{N}{p}) раз зачеркиваем числа делящиеся на простое число (p). Если бы все числа были простыми, то мы бы как раз получили (N log N) из формули выше. Но у нас будут не все слагаемые оттуда, только с простым (p), поэтому посмотрим чуть более точно.

Известно, что простых чисел до (N) примерно (frac{N}{log N}), а значит допустим, что k-ое простое число примерно равно (k ln k). Тогда

[sum_{substack{2 leq p leq N \ text{p is prime}}} frac{N}{p} sim frac{1}{2} + sum_{k = 2}^{frac{N}{ln N}} frac{N}{k ln k} sim int_{2}^{frac{N}{ln N}} frac{N}{k ln k} dk =N(lnlnfrac{N}{ln N} – lnln 2) sim N(lnln N – lnlnln N) sim N lnln N]

Но вообще-то решето можно сделать и линейным.

Задание

Решите 5 первых задач из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34271

Линейное решето Эратосфена*

Наша цель — для каждого числа до (N) посчитать его минимальный простой делитель. Будем хранить его в массиве min_d. Параллельно будем хранить и список всех найденных простых чисел primes – это ровно те числа (x), у которых (min_d[x] = x).

Основное утверждение такое:

Пусть у числа (M) минимальный делитель равен (a). Тогда, если (M) составное, мы хотим вычеркнуть его ровно один раз при обработке числа (frac{M}{a}).

Мы также перебираем число (i) от (2) до (N). Если (min_d[i]) равно 0 (то есть мы не нашли ни один делитель у этого числа еще), значит оно простое – добавим в primes и сделаем (min_d[i] = i).

Далее мы хотим вычеркнуть все числа (i times k) такие, что (k) – это минимальный простой делитель этого числа. Из этого следует, что необходимо и достаточно перебрать (k) в массиве primes, и только до тех пор, пока (k < min_d[i]). Ну и перестать перебирать, если (i times k > N).

Алгоритм пометит все числа по одному разу, поэтому он корректен и работает за (O(N)).

N = 30
primes = []
min_d = [0] * (N + 1)

for i in range(2, N + 1):
    if min_d[i] == 0:
        min_d[i] = i
        primes.append(i)
    for p in primes:
        if p > min_d[i] or i * p > N:
            break
        min_d[i * p] = p
    print(i, min_d)
print(min_d)
print(primes)
2 [0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 [0, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4 [0, 0, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5 [0, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0]
6 [0, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0]
7 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0]
8 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0]
9 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 5, 0, 3, 0, 0, 0]
10 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 5, 0, 3, 0, 0, 0]
11 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 0, 5, 0, 3, 0, 0, 0]
12 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 0, 3, 0, 0, 0]
13 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 0, 0, 0]
14 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 0]
15 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
16 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
17 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
18 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
19 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
20 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
21 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
22 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
23 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
24 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
25 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
26 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
27 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
28 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
29 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2]
30 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2]
[0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Этот алгоритм работает асимптотически быстрее, чем обычное решето. Но на практике, если писать обычное решето Эратсфена с оптимизациями, то оно оказывается быстрее линейнего. Также линейное решето занимает гораздо больше памяти – ведь в обычном решете можно хранить просто (N) бит, а здесь нам нужно (N) чисел и еще массив primes.

Зато один из «побочных эффектов» алгоритма — он неявно вычисляет факторизацию всех чисел от (1) до (N). Ведь зная минимальный простой делитель любого числа от (1) до (N) можно легко поделить на это число, посмотреть на новый минимальный простой делитель и так далее.

НОД и НОК

Введем два определения.

Наибольший общий делитель (НОД) чисел (a_1, a_2, ldots, a_n) — это максимальное такое число (x), что все (a_i) делятся на (x).

Наименьшее общее кратное (НОК) чисел (a_1, a_2, ldots, a_n) — это минимальное такое число (x), что (x) делится на все (a_i).

Например, * НОД(18, 30) = 6 * НОД(60, 180, 315) = 15 * НОД(1, N) = 1 * НОК(12, 30) = 6 * НОК(1, 2, 3, 4) = 12 * НОК(1, (N)) = (N)

Зачем они нужны? Например, они часто возникают в задачах.

Условие: Есть (N) шестеренок, каждая (i)-ая зацеплена с ((i-1))-ой. (i)-ая шестеренка имеет (a_i) зубчиков. Сколько раз нужно повернуть полносьтю первую шестеренку, чтобы все остальные шестеренки тоже вернулись на изначальное место?

Решение: Когда одна шестеренка крутится на 1 зубчик, все остальные тоже крутятся на один зубчик. Нужно найти минимальное такое число зубчиков (x), что при повороте на него все шестеренки вернутся в изначальное положение, то есть (x) делится на все (a_i), то есть это НОК((a_1, a_2, ldots, a_N)). Ответом будет (frac{x}{a_1}).

Еще пример задачи на применение НОД и НОК:

Условие: Город — это прямоугольник (n) на (m), разделенный на квадраты единичного размера. Вертолет летит из нижнего левого угла в верхний правый по прямой. Вертолет будит людей в квартале, когда он пролетает строго над его внутренностью (границы не считаются). Сколько кварталов разбудит вертолёт?

Решение: Вертолет пересечет по вертикали ((m-1)) границу. С этим ничего не поделать — каждое считается как новое посещение какого-то квартала. По горизонтали то же самое — ((n-1)) переход в новую ячейку будет сделан.

Однако еще есть случай, когда он пересекает одновременно обе границы (то есть пролетает над каким-нибудь углом) — ровно тот случай, когда нового посещения квартала не происходит. Сколько таких будет? Ровно столько, сколько есть целых решений уравнения (frac{n}{m} = frac{x}{y}). Мы как бы составили уравнение движения вертолёта и ищем, в скольки целых точках оно выполняется.

Пусть (t = НОД(n, m)), тогда (n = at, m = bt).

Тогда (frac{n}{m} = frac{a}{b} = frac{x}{y}). Любая дробь с натуральными числителем и знаменателем имеет ровно одно представление в виде несократимой дроби, так что (x) должно делиться на (a), а (y) должно делиться на (b). А значит, как ответ подходят ((a, b), (2a, 2b), (3a, 3b), cdots, ((t-1)a, (t-1)b)). Таких ответов ровно (t = НОД(n, m))

Значит, итоговый ответ: ((n-1) + (m-1) – (t-1)).

Кстати, когда (НОД(a, b) = 1), говорят, что (a) и (b) взаимно просты.

Алгоритм Евклида

Осталось придумать, как искать НОД и НОК. Понятно, что их можно искать перебором, но мы хотим хороший быстрый способ.

Давайте для начала научимся искать (НОД(a, b)).

Мы можем воспользоваться следующим равенством: [НОД(a, b) = НОД(a, b – a), b > a]

Оно доказывается очень просто: надо заметить, что множества общих делителей у пар ((a, b)) и ((a, b – a)) совпадают. Почему? Потому что если (a) и (b) делятся на (x), то и (b-a) делится на (x). И наоборот, если (a) и (b-a) делятся на (x), то и (b) делится на (x). Раз множства общих делитей совпадают, то и максимальный делитель совпадает.

Из этого равенства сразу следует следующее равенство: [НОД(a, b) = НОД(a, b operatorname{%} a), b > a]

(так как (НОД(a, b) = НОД(a, b – a) = НОД(a, b – 2a) = НОД(a, b – 3a) = ldots = НОД(a, b operatorname{%} a)))

Это равенство дает идею следующего рекурсивного алгоритма:

[НОД(a, b) = НОД(b operatorname{%} a, a) = НОД(a operatorname{%} , (b operatorname{%} a), b operatorname{%} a) = ldots]

Например: [НОД(93, 36) = ] [= НОД(36, 93spaceoperatorname{%}36) = НОД(36, 21) = ] [= НОД(21, 15) = ] [= НОД(15, 6) = ] [= НОД(6, 3) = ] [= НОД(3, 0) = 3]

Задание:

Примените алгоритм Евклида и найдите НОД чисел: * 1 и 500000 * 10, 20 * 18, 60 * 55, 34 * 100, 250

По-английски наибольший общий делитель — greatest common divisor. Поэтому вместо НОД будем в коде писать gcd.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(1, 500000))
print(gcd(10, 20))
print(gcd(18, 60))
print(gcd(55, 34))
print(gcd(100, 250))
print(gcd(2465473782, 12542367456))
1
10
6
1
50
6

Вообще, в C++ такая функция уже есть в компиляторе g++ — называется __gcd. Если у вас не Visual Studio, то, скорее всего, у вас g++. Вообще, там много всего интересного.

А за сколько оно вообще работает?

Задание

Докажите, что алгоритм Евклида для чисел (N), (M) работает за (O(log(N+M))).

Кстати, интересный факт: самыми плохими входными данными для алгоритма Евклида являются числа Фибоначчи. Именно там и достигается логарифм.

Как выразить НОК через НОД

(НОК(a, b) = frac{ab}{НОД(a, b)})

По этой формуле можно легко найти НОК двух чисел через их произведение и НОД. Почему она верна?

Посмотрим на разложения на простые множители чисел a, b, НОК(a, b), НОД(a, b).

[ a = p_1^{a_1}times p_2^{a_2}timesldotstimes p_n^{a_n} ] [ b = p_1^{b_1}times p_2^{b_2}timesldotstimes p_n^{b_n} ] [ ab = p_1^{a_1+b_1}times p_2^{a_2+b_2}timesldotstimes p_n^{a_n+b_n} ]

Из определений НОД и НОК следует, что их факторизации выглядят так: [ НОД(a, b) = p_1^{min(a_1, b_1)}times p_2^{min(a_2, b_2)}timesldotstimes p_n^{min(a_n, b_n)} ] [ НОК(a, b) = p_1^{max(a_1, b_1)}times p_2^{max(a_2, b_2)}timesldotstimes p_n^{max(a_n, b_n)} ]

Тогда посчитаем (НОД(a, b) times НОК(a, b)): [ НОД(a, b)НОК(a, b) = p_1^{min(a_1, b_1)+max(a_1, b_1)}times p_2^{min(a_2, b_2)+max(a_2, b_2)}timesldotstimes p_n^{min(a_n, b_n)+max(a_n, b_n)} =] [ = p_1^{a_1+b_1}times p_2^{a_2+b_2}timesldotstimes p_n^{a_n+b_n} = ab]

Формула доказана.

Как посчитать НОД/НОК от более чем 2 чисел

Для того, чтобы искать НОД или НОК у более чем двух чисел, достаточно считать их по цепочке:

(НОД(a, b, c, d, ldots) = НОД(НОД(a, b), c, d, ldots))

(НОК(a, b, c, d, ldots) = НОК(НОК(a, b), c, d, ldots))

Почему это верно?

Ну просто множество общих делителей (a) и (b) совпадает с множеством делителей (НОД(a, b)). Из этого следует, что и множество общих делителей (a), (b) и еще каких-то чисел совпадает с множеством общих делителей (НОД(a, b)) и этих же чисел. И раз совпадают множества общих делителей, то и наибольший из них совпадает.

С НОК то же самое, только фразу “множество общих делителей” надо заменить на “множество общих кратных”.

Задание

Решите задачи F, G, H, I из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34271

Расширенный алгоритм Евклида*

Очень важным для математики свойством наибольшего общего делителя является следующий факт:

Для любых целых (a, b) найдутся такие целые (x, y), что (ax + by = d), где (d = gcd(a, b)).

Из этого следует, что существует решение в целых числах, например, у таких уравнений: * (8x + 6y = 2) * (4x – 5y = 1) * (116x + 44y = 4) * (3x + 11y = -1)

Мы сейчас не только докажем, что решения у таких уравнений существуют, но и приведем быстрый алгоритм нахождения этих решений. Здесь нам вновь пригодится алгоритм Евклида.

Рассмотрим один шаг алгоритма Евклида, преобразующий пару ((a, b)) в пару ((b, a operatorname{%} b)). Обозначим (r = a operatorname{%} b), то есть запишем деление с остатком в виде (a = bq + r).

Предположим, что у нас есть решение данного уравнения для чисел (b) и (r) (их наибольший общий делитель, как известно, тоже равен (d)): [bx_0 + ry_0 = d]

Теперь сделаем в этом выражении замену (r = a – bq):

[bx_0 + ry_0 = bx_0 + (a – bq)y_0 = ay_0 + b(x_0 – qy_0)]

Tаким образом, можно взять (x = y_0), а (y = (x_0 – qy_0) = (x_0 – (a operatorname{/} b)y_0)) (здесь (/) обозначает целочисленное деление).

В конце алгоритма Евклида мы всегда получаем пару ((d, 0)). Для нее решение требуемого уравнения легко подбирается — (d * 1 + 0 * 0 = d). Теперь, используя вышесказанное, мы можем идти обратно, при вычислении заменяя пару ((x, y)) (решение для чисел (b) и (a operatorname{%} b)) на пару ((y, x – (a / b)y)) (решение для чисел (a) и (b)).

Это удобно реализовывать рекурсивно:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = extended_gcd(b, a % b)
    return d, y, x - (a // b) * y

a, b = 3, 5
res = extended_gcd(a, b)
print("{3} * {1} + {4} * {2} = {0}".format(res[0], res[1], res[2], a, b))
3 * 2 + 5 * -1 = 1

Но также полезно и посмотреть, как будет работать расширенный алгоритм Евклида и на каком-нибудь конкретном примере. Пусть мы, например, хотим найти целочисленное решение такого уравнения: [116x + 44y = 4] [(2times44+28)x + 44y = 4] [44(2x+y) + 28x = 4] [44x_0 + 28y_0 = 4] Следовательно, [x = y_0, y = x_0 – 2y_0] Будем повторять такой шаг несколько раз, получим такие уравнения: [116x + 44y = 4] [44x_0 + 28y_0 = 4, x = y_0, y = x_0 – 2y_0] [28x_1 + 16y_1 = 4, x_0 = y_1, y_0 = x_1 – y_1] [16x_2 + 12y_2 = 4, x_1 = y_2, y_1 = x_2 – y_2] [12x_3 + 4y_3 = 4, x_2 = y_3, y_2 = x_3 – y_3] [4x_4 + 0y_4 = 4, x_3 = y_4, y_3 = x_4 – 3 y_4] А теперь свернем обратно: [x_4 = 1, y_4 = 0] [x_3 = 0, y_3 =1] [x_2 = 1, y_2 =-1] [x_1 = -1, y_1 =2] [x_0 = 2, y_0 =-3] [x = -3, y =8]

Действительно, (116times(-3) + 44times8 = 4)

Задание

Решите задачу J из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34273

Операции по модулю

Выражение (a equiv b pmod m) означает, что остатки от деления (a) на (m) и (b) на (m) равны. Это выражение читается как «(a) сравнимо (b) по модулю (m)».

Еще это можно опрделить так: (a) сравнимо c (b) по модулю (m), если ((a – b)) делится на (m).

Все целые числа можно разделить на классы эквивалентности — два числа лежат в одном классе, если они сравнимы по модулю (m). Говорят, что мы работаем в «кольце остатков по модулю (m)», и в нем ровно (m) элементов: (0, 1, 2, cdots, m-1).

Сложение, вычитение и умножение по модулю определяются довольно интуитивно — нужно выполнить соответствующую операцию и взять остаток от деления.

С делением намного сложнее — поделить и взять по модулю не работает. Об этом подробнее поговорим чуть дальше.

a = 30
b = 50
mod = 71

print('{} + {} = {} (mod {})'.format(a, b, (a + b) % mod, mod))
print('{} - {} = {} (mod {})'.format(a, b, (a - b) % mod, mod)) # на C++ это может не работать, так как модуль от отрицательного числа берется странно
print('{} - {} = {} (mod {})'.format(a, b, (a - b + mod) % mod, mod)) # на C++ надо писать так, чтобы брать модулю от гарантированно неотрицательного числа
print('{} * {} = {} (mod {})'.format(a, b, (a * b) % mod, mod))
# print((a / b) % mod) # а как писать это, пока неясно
30 + 50 = 9 (mod 71)
30 - 50 = 51 (mod 71)
30 - 50 = 51 (mod 71)
30 * 50 = 9 (mod 71)

Задание

Посчитайте: * (2 + 3 pmod 5) * (2 * 3 pmod 5) * (2 ^ 3 pmod 5) * (2 – 4 pmod 5) * (5 + 5 pmod 6) * (2 * 3 pmod 6) * (3 * 3 pmod 6)

Для умножения (в C++) нужно ещё учитывать следующий факт: при переполнении типа всё ломается (разве что если вы используете в качестве модуля степень двойки).

  • int вмещает до (2^{31} – 1 approx 2 cdot 10^9).
  • long long вмещает до (2^{63} – 1 approx 8 cdot 10^{18}).
  • long long long в плюсах нет, при попытке заиспользовать выдает ошибку long long long is too long.
  • Под некоторыми компиляторами и архитектурами доступен int128, но не везде и не все функции его поддерживают (например, его нельзя вывести обычными методами).

Зачем нужно считать ответ по модулю

Очень часто в задаче нужно научиться считать число, которое в худшем случае гораздо больше, чем (10^{18}). Тогда, чтобы не заставлять вас писать длинную арифметику, автор задачи часто просит найти ответ по модулю большого числа, обычно (10^9 + 7)

Кстати, вместо того, чтобы писать (1000000007) удобно просто написать (1e9 + 7). (1e9) означает (1 times 10^9)

int mod = 1e9 + 7; # В C++
cout << mod;
1000000007
N = 1e9 + 7 # В питоне такое число становится float
print(N)
print(int(N))
1000000007.0
1000000007

Быстрое возведение в степень

Задача: > Даны натуральные числа (a, b, c < 10^9). Найдите (a^b) (mod (c)).

Мы хотим научиться возводить число в большую степень быстро, не просто умножая (a) на себя (b) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.

Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):

  • (3^2)
  • (3^4)
  • (3^8)
  • (3^{16})
  • (3^{32})
  • (3^{33})
  • (3^{66})
  • (3^{132})
  • (3^{133})
  • (3^{266})
  • (3^{532})
  • (3^{533})
  • (3^{1066})

Да, здесь специально приведена такая последовательность, в которой каждое следующее число легко считается через предыдущее: его либо нужно умножить на (a=3), либо возвести в квадрат. Так и получается рекурсивный алгоритм:

  • (a^0 = 1)
  • (a^{2k}=(a^{k})^2)
  • (a^{2k+1}=a^{2k}times a)

Нужно только после каждой операции делать mod: * (a^0 pmod c = 1) * (a^{2k} pmod c = (a^{k} pmod c)^2 pmod c) * (a^{2k+1} pmod c = ((a^{2k}pmod c) times a) pmod c)

Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)

Асимптотика этого алгоритма, очевидно, (O(log c)) – за каждые две итерации число уменьшается хотя бы в 2 раза.

Задание

Решите задачу K из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34271

Задание

Решите как можно больше задач из практического контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34273

Деление по модулю*

Давайте все-таки научимся не только умножать, но и делить по простому модулю. Вот только что это значит?

(a / b) = (a times b^{-1}), где (b^{-1}) – это обратный элемент к (b).

Определение: (b^{-1}) – это такое число, что (bb^{-1} = 1)

Утверждение: в кольце остатков по простому модулю (p) у каждого остатка (кроме 0) существует ровно один обратный элемент.

Например, обратный к (2) по модулю (5) это (3) ((2 times 3 = 1 pmod 5)))

Задание

Найдите обратный элемент к: * числу (3) по модулю (5) * числу (3) по модулю (7) * числу (1) по модулю (7) * числу (2) по модулю (3) * числу (9) по модулю (31)

Давайте докажем это утверждение: надо заметить, что если каждый ненулевой остаток (1, 2, ldots, (p-1)) умножить на ненулевой остаток (a), то получатся числа (a, 2a, ldots, (p-1)a) – и они все разные! Они разные, потому что если (xa = ya), то ((x-y)a = 0), а значит ((x – y) a) делится на (p), (a) – ненулевой остаток, а значит (x = y), и это не разные числа. И из того, что все числа получились разными, это все ненулевые, и их столько же, следует, что это ровно тот же набор чисел, просто в другом порядке!

Из этого следует, что среди этих чисел есть (1), причем ровно один раз. А значит существует ровно один обратный элемент (a^{-1}). Доказательство закончено.

Это здорово, но этот обратный элемент еще хочется быстро находить. Быстрее, чем за (O(p)).

Есть несколько способов это сделать.

Через малую теорему Ферма

Малая теорема Ферма: > (a^{p-1} = 1 pmod p), если (p) – простое, (a neq 0 pmod p)).

Доказательство: В предыдущем пункте мы выяснили, что множества чисел (1, 2, ldots, (p-1)) и (a, 2a, ldots, (p-1)a) совпадают. Из этого следует, что их произведения тоже совпадают по модулю: ((p-1)! = a^{p-1} (p-1)! pmod p).

((p-1)!neq 0 pmod p) а значит на него можно поделить (это мы кстати только в предыдущем пункте доказали, поделить на число – значит умножить на обратный к нему, который существует).

А значит, (a^{p – 1} = 1 pmod p).

Как это применить Осталось заметить, что из малой теоремы Ферма сразу следует, что (a^{p-2}) – это обратный элемент к (a), а значит мы свели задачу к возведению (a) в степень (p-2), что благодаря быстрому возведению в степень мы умеем делать за (O(log p)).

Обобщение У малой теоремы Ферма есть обобщение для составных (p):

Теорема Эйлера: > (a^{varphi(p)} = 1 pmod p), (a) – взаимно просто с (p), а (varphi(p)) – это функция Эйлера (количество чисел, меньших (p) и взаимно простых с (p)).

Доказывается теорема очень похоже, только вместо ненулевых остатков (1, 2, ldots, p-1) нужно брать остатки, взаимно простые с (p). Их как раз не (p-1), а (varphi(p)).

Для нахождения обратного по этой теореме достаточно посчитать функцию Эйлера (varphi(p)) и найти (a^{-1} = a^{varphi(p) – 1}).

Но с этим возникают большие проблемы: посчитать функцию Эйлера сложно. Более того, на предполагаемой невозможности быстро ее посчитать построены некоторые криптографические алгоритм типа RSA. Поэтому быстро делить по составному модулю этим способом не получится.

Через расширенный алгоритм Евклида

Этим способом легко получится делить по любому модулю! Рекомендую.

Пусть мы хотим найти (a^{-1} pmod p), (a) и (p) взаимно простые (а иначе обратного и не будет существовать).

Давайте найдем корни уравнения

[ax + py = 1]

Они есть и находятся расширенным алгоритмом Евклида за (O(log p)), так как (НОД(a, p) = 1), ведь они взаимно простые.

Тогда если взять остаток по модулю (p):

[ax = 1 pmod p]

А значит, найденный (x) и будет обратным элементом к (a).

То есть надо просто найти (x) из решения того уравнения по модулю (p). Можно брать по модулю прямо походу решения уравнения, чтобы случайно не переполниться.

Источник

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

История[править | править код]

Этот метод описан во «Введении в арифметику» Никомаха Герасского. Никомах называет автором метода Эратосфена. То же делает и Ямвлих в своём комментарии к этому сочинению Никомаха.

Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые[2].

Никомах,[1] во 2-м веке н.э., объясняет, что метод решета “высеивает” простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа n каждое n-ное число в ряду нечётных чисел, начиная с n. Символически,

 Primes = {3,5,7,9,...}  Composites
 Composites = { 3n,5n,7n,9n,... for n in {3,5,7,9,...} }

Британец Хорслей,[3] 16 веков спустя, горячо критикует это описание, заявляя что “истинный” метод Эратосфена “наверняка” был “гораздо умнее”, начиная с квадратов простых чисел прямо в процессе их распознавания:

 Composites = { n²,n²+2n,n²+4n,... for n in Primes }

Алгоритм[править | править код]

Анимация шагов алгоритма Эратосфена для нахождения простых чисел до 120

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

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

Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать, начиная сразу с числа p2, потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, а они уже зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[3] Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.

Пример для n = 30[править | править код]

Запишем натуральные числа, начиная от 2, до 30 в ряд: 

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 2 (то есть, каждое второе, начиная с 22 = 4): 

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 3 (то есть, каждое третье, начиная с 32 = 9): 

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 5 (то есть, каждое пятое, начиная с 52 = 25): 

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30, поэтому на этом работа завершена. Все составные числа уже зачеркнуты: 

2  3     5     7           11    13          17    19          23                29

Псевдокод[править | править код]

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде[4][5]: 

Вход: натуральное число n
Выход: все простые числа от 2 до n.

Пусть A — булевый массив, индексируемый числами от 2 до n, 
изначально заполненный значениями true.

 для i = 2, 3, 4, ..., пока i2 ≤ n:
  если A[i] = true:
    для j = i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
      назначить A[j] := false

 возвращаем: все числа i, для которых A[i] = true.

Сложность алгоритма[править | править код]

Сложность алгоритма составляет O(nlog(log n)) операций при составлении таблицы простых чисел до n[6].

Доказательство сложности[править | править код]

При выбранном nin mathbb {N} для каждого простого pin {mathbb {P}}colon pleq n будет выполняться внутренний цикл[7], который совершит {frac {n}{p}} действий. Сложность алгоритма можно получить из оценки следующей величины:

sum limits _{{pin {mathbb {P}}colon pleq n}}{{frac {n}{p}}}=ncdot sum limits _{{pin {mathbb {P}}colon pleq n}}{{frac {1}{p}}}

Так как количество простых чисел, меньших либо равных n, оценивается как {frac {n}{ln n}}, и, как следствие, k-е простое число примерно равно kln k, то сумму можно преобразовать:

{displaystyle sum limits _{pin mathbb {P} colon pleq n}{frac {1}{p}}approx {frac {1}{2}}+sum limits _{k=2}^{frac {n}{ln n}}{frac {1}{kln k}}}

Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на ноль. Данную сумму можно оценить интегралом

{displaystyle {frac {1}{2}}+sum _{k=2}^{frac {n}{ln n}}{frac {1}{kln k}}approx int limits _{2}^{frac {n}{ln n}}{frac {1}{kln k}},dk=ln ln k{Bigr |}_{2}^{frac {n}{ln n}}=ln ln {frac {n}{ln n}}-ln ln 2=ln(ln n-ln ln n)-ln ln 2approx ln ln n}

В итоге получается для изначальной суммы:

{displaystyle sum limits _{pin mathbb {P} colon pleq n}{frac {n}{p}}approx nln ln n+o(n)}

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[8].

Модификации метода[править | править код]

Неограниченный, постепенный вариант[править | править код]

В этом варианте простые числа вычисляются последовательно, без ограничения сверху,[9] как числа, находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p, начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p)[3]. Может быть представлен абстрактно в парадигме потоков данных как

 primes = {2,3,...}  { p², p²+p, ... for p in primes }

используя нотацию абстракции списков, где обозначает разницу между арифметическими прогрессиями.

Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.

Более конкретный псевдокод с поэтапным отсеиванием, в неэффективной реализации, для простоты сравнения с нижеследующими вариантами: 

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve (xs  [p², p²+p..])]

Более эффективный вариант отделяет на каждом шагу из начала списка не одно лишь первое число, а сразу все числа не превосходящие квадрата очередного простого числа.

Перебор делителей[править | править код]

Решето Эратосфена часто путают с алгоритмами, которые поэтапно отфильтровывают[en] составные числа, тестируя каждое из чисел-кандидатов на делимость по одному простому числу на каждом этапе.[10]

Широко известный функциональный код Дэвида Тёрнера 1975 г.[11] часто принимают за решето Эратосфена,[10] но на самом деле[9] это неоптимальный вариант с перебором делителей: 

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve [x in xs if x%p > 0]]

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

Сегментированное решето[править | править код]

Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году).[5] При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок[en].

Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.[12] Данный метод известен с 1970-х годов и работает следующим образом:[5][13]

  1. Разделяем диапазон от 2 до n на отрезки (сегменты) некоторой длины Δ ≤ √n.
  2. Находим все простые числа в первом отрезке, используя обычное решето.
  3. Каждый из последующих отрезков оканчивается на некотором числе m. Находим все простые числа в отрезке следующим образом:
    1. Создаем булевый массив размера Δ
    2. Для каждого простого числа p ≤ √m из уже найденных, отмечаем в массиве как «непростые» все числа кратные p, перебирая числа с шагом в p, начиная с наименьшего кратного p числа в данном отрезке.

Если число Δ выбрано равным √n, то сложность алгоритма по памяти оценивается как O(√n), а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.[13]

Для случаев, когда n настолько велико, что все просеиваемые простые числа меньшие √n не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.[14]

Решето Эйлера[править | править код]

Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978 г. как решето с линейным временем работы (см. ниже).

Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, результаты произведения которого на каждое число в списке помечаются для последующего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь: 

[2] (3) 5  7  9 11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
[3]    (5) 7    11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
[4]       (7)   11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
[5]            (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
[...]

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

В псевдокоде, 

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve (xs  [p², ...p*xs])]

Решето только по нечётным числам[править | править код]

Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое).

В псевдокоде:

 primes = [2, ...sieve [3,5..]] where
    sieve [p, ...xs] = [p, ...sieve (xs  [p², p²+2p..])]

Это можно обобщить на числа взаимно простые не только с 2 (то есть нечетные числа), но также и с 3, 5, и т. д..

Уменьшение объёма потребляемой памяти[править | править код]

Алгоритм Эратосфена фактически оперирует с n битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня n переменных булевского типа не как n байт, а как n бит, то есть n/8 байт памяти.

Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.

Решето Эратосфена с линейным временем работы[править | править код]

Нижеследующий алгоритм находит составные числа как перечисление формулы

{ (piqjrk...) for p,q,r,... in primes, where i+j+k+... > 1 }

Этот алгоритм обнаруживает для каждого числа i в отрезке [2…n] его минимальный простой делитель lp[i] (lp от англ. least prime).

Также поддерживается список всех простых чисел — массив pr[], поначалу пустой. В ходе работы алгоритма этот массив будет постепенно заполняться.

Изначально все величины lp[i] заполним нулями.

Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:

  • lp[i] = 0: это означает, что число i — простое, так как для него так и не обнаружилось других делителей.

Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].

  • lp[i] ≠ 0: это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].

В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.

Утверждается, что для этого можно поступить таким образом. Рассматриваются числа вида x = p ⋅ i, где p последовательно равно всем простым числам не превосходящим lp[i] (как раз для этого понадобилось хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение lp[x] — оно должно быть равно p[15].

Псевдокод[править | править код]

 Вход: натуральное число n

Пусть pr - целочисленный массив, поначалу пустой;
      lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями

 для i := 2, 3, 4, ..., до n: 
   если lp[i] = 0:
       lp[i] := i
       pr[] += {i}
   для p из pr пока p ≤ lp[i] и p*i ≤ n:
       lp[p*i] := p

Выход: все числа в массиве pr.

Сложность алгоритма на практике[править | править код]

Решето Эратосфена является популярным способом оценки производительности компьютера.[16] Как видно из вышеизложенного доказательства сложности алгоритма, избавившись от константы и слагаемого очень близкого к нулю (ln (ln n – ln ln n) – ln ln 2 ≈ ln ln n), временная сложность вычисления всех простых чисел меньше n аппроксимируется следующим соотношением O(n ln ln n). Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется O(n).[17]

Сегментированная версия имеет ту же операционную сложность O(n ln ln n),[8]. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен O(√n/ln n).[18]
Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за O(n) операций и занимает O(√n ln ln n/ln n) бит в памяти.[17][19][18]

На практике оказывается, что оценка ln ln n не очень точна даже для максимальных практических диапазонов таких как 1016.[19] Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения.[8] Таким образом очень медленно растущий член ln ln n не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока n не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания.[8] Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.[19]

Решето Эратосфена работает быстрее, чем часто сравниваемое с ним решето Аткина только для значений n меньших 10 10 .[20] Сказанное справедливо при условии, что операции занимают примерно одно и то же время в циклах центрального процессора, а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом.[21] С учетом этого предположения получается, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для n свыше 10 13 , но при таких диапазонах просеивания потребуется занять огромное пространство в оперативной памяти, даже если была использована «битовая упаковка».[21] Однако раздел о сегментированной версии решета Эратосфена показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операцию, между двумя алгоритмами не выполняется при сегментации.[13][20] В свою очередь это приводит к тому, что решето Аткина (несегментированное) работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго.

Использование нотации O большого также не является правильным способом сравнения практических характеристик даже для вариаций решета Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов.[8] Например, одна из вариаций решета Эратосфена известная как решето Притчарда[17] имеет производительность O(n),[19] но её базовая реализация требует либо алгоритма «одного большого массива»[18] (то есть использования обычного массива, в котором хранятся все числа до n), который ограничивает его диапазон использования до объёма доступной памяти, либо он должен быть сегментирован для уменьшения использования памяти. Работа Притчарда уменьшила требования к памяти до предела, но платой за данное улучшение по памяти является усложнение вычислений, что приводит увеличению операционной сложности алгоритмов.[19]

Популярным способом ускорения алгоритмов, работающих с большими массивами чисел, является разного рода факторизация.[22] Применение методов факторизации даёт значительное уменьшение операционной сложности за счёт оптимизации входного массива данных.[23][22] Для индексных алгоритмов часто используют кольцевую факторизацию.[23][24] Рассматриваемые в данной статье алгоритмы нахождения всех простых чисел до заданного n подобные решету Эратосфена относятся к индексным, что позволяет применять к ним метод кольцевой факторизации.[25]

Несмотря на теоретическое ускорение, получаемое с помощью кольцевой факторизации, на практике существуют факторы, которые не учитываются при расчётах, но способны оказать существенное влияние на поведение алгоритма, что в результате может не дать ожидаемого прироста в быстродействии.[26] Рассмотрим наиболее существенные из них:

  • Умножение и деление. При аналитических расчётах предполагается, что скорость выполнения арифметических операций равноценна. Но на самом деле это не так, и умножение, и деление выполняются гораздо медленнее, чем сложение и вычитание. Таким образом данный фактор никак не влияет на решето Эратосфена, поскольку оно использует только сложение и вычитание, но является весьма существенным для решета Питчарда (один из результатов усложнения вычислений упомянутого выше).[27]
  • Оптимизация компилятора. Компилятор оптимизирует на стадии компиляции все программы для более корректного исполнения машиной. Но часто бывает очень сложно сказать, какой вклад даёт данная оптимизация, и будет ли этот вклад одинаковым для двух различных алгоритмов.[28]
  • Кэш. Процессор использует кэш, чтобы ускорить извлечение инструкций и данных из памяти. Наличие кэша приводит к тому, что программы, использующие локализованные ссылки, будут работать быстрее. Но алгоритмы просеивания простых чисел, которые используют факторизацию высокой степени, часто генерируют случайные ссылки в память, что снижает их производительность.[28]

Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов n и разных степеней кольцевой факторизации. Ei и Pi обозначения для решета Эратосфена и Питчарда соответственно, где индекс i означает степень кольцевой факторизации. E0 и P0 означают отсутствие факторизации.[28]

n E0 E1 E2 E3 E4 E5
500 0.00043 0.00029 0.00027 0.00048 0.00140 0.01035
5000 0.00473 0.00305 0.00254 0.00293 0.00551 0.03207
50000 0.05156 0.03281 0.02617 0.02578 0.03164 0.10663
500000 0.55817 0.35037 0.28240 0.28358 0.28397 0.47028
5000000 6.06719 3.82905 3.20722 3.25214 3.28104 3.38455

Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации E2. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.

n P0 P1 P2 P3 P4 P5
500 0.00147 0.00074 0.00050 0.00051 0.00095 0.00649
5000 0.01519 0.00777 0.00527 0.00453 0.00430 0.00973
50000 0.15507 0.08203 0.05664 0.04843 0.04180 0.04413
500000 1.60732 0.86254 0.61597 0.53825 0.47146 0.43787
5000000 16.47706 9.00177 6.57146 5.83518 5.27427 4.88251

С увеличением n соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне n = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.[19]

См. также[править | править код]

  • Решето Сундарама
  • Решето Аткина
  • Корекурсия

Примечания[править | править код]

  1. ↑ 1 2 Никомах Герасский, Введение в арифметику, I, XIII, 2. по-гречески, по-русски
  2. ↑ Депман И. Я. История арифметики. Пособие для учителей. — М.: Просвещение, 1965. — С. 133. — 34 000 экз.
  3. ↑ 1 2 3 Horsley, Rev. Samuel, F. R. S., “Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, ” Philosophical Transactions (1683—1775), Vol. 62. (1772), pp. 327—347 Архивная копия от 2 октября 2018 на Wayback Machine.
  4. ↑ Sedgewick, Robert. Algorithms in C++ (неопр.). — Addison-Wesley, 1992. — ISBN 0-201-51059-6., p. 16.
  5. ↑ 1 2 3 Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
  6. ↑ Pritchard, Paul, “Linear prime-number sieves: a family tree, ” Sci. Comput. Programming 9:1 (1987), pp. 17-35.
  7. ↑ Строго говоря, внутренний цикл выполняется для каждого простого {displaystyle pin mathbb {P} colon pleq ({sqrt {n}})}, но {displaystyle O(log(log n))} = {displaystyle O(log(log({sqrt {n}})))}, поэтому, традиционно, для краткости, квадратный корень опускают.
  8. ↑ 1 2 3 4 5 Hardy and Wright “An Introduction to the Theory of Numbers, p. 349
  9. ↑ 1 2 O’Neill, Melissa E., «The Genuine Sieve of Eratosthenes» Архивная копия от 9 ноября 2017 на Wayback Machine, Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004.
  10. ↑ 1 2 Colin Runciman, «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes», Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь Архивная копия от 19 октября 2012 на Wayback Machine.
  11. ↑ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0)
  12. ↑ Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121-24.
  13. ↑ 1 2 3 Bays, Carter; Hudson, Richard H. The segmented sieve of Eratosthenes and primes in arithmetic progressions to 1012 (англ.) // BIT : journal. — 1977. — Vol. 17, no. 2. — P. 121—127. — doi:10.1007/BF01932283.
  14. ↑ J. Sorenson, The pseudosquares prime sieve Архивная копия от 17 октября 2012 на Wayback Machine, Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
  15. ↑ David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]
  16. ↑ Peng, T. A.. One Million Primes Through the Sieve, BYTE (Fall 1985), С. 243–244. Дата обращения: 19 марта 2016.
  17. ↑ 1 2 3 Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18-23. MR: 600730
  18. ↑ 1 2 3 Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4
    (1983), 332—344. MR: 729229
  19. ↑ 1 2 3 4 5 6 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477—485. MR: 685983
  20. ↑ 1 2 A. O. L. ATKIN AND D. J. BERNSTEIN. PRIME SIEVES USING BINARY QUADRATIC FORMS // MATHEMATICS OF COMPUTATION. Архивировано 24 декабря 2017 года.
  21. ↑ 1 2 Meertens, Lambert. Calculating the Sieve of Eratosthenes // Journal of
    functional programming.
  22. ↑ 1 2 В.А. Минаев, Н.П. Васильев, В.В. Лукьянов, С.А. Никонов, Д.В. Никеров. [http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf ИНДЕКСНЫЕ АЛГОРИТМЫ
    ВЫЧИСЛЕНИЯ ПРОСТЫХ ЧИСЕЛ
    С ИСПОЛЬЗОВАНИЕМ МЕТОДА
    КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ] // ВЕСТНИК. — 2013. — № 4. — С. 29. Архивировано 22 декабря 2017 года.
  23. ↑ 1 2 Jonathan Sorenson. An Analysis of Two Prime Number Sieves // Computer Sciences Department University of Wisconsin-Madison. — С. 8—10.
  24. ↑ В.А. Минаев, Н.П. Васильев, В.В. Лукьянов, С.А. Никонов, Д.В. Никеров. [http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf ИНДЕКСНЫЕ АЛГОРИТМЫ
    ВЫЧИСЛЕНИЯ ПРОСТЫХ ЧИСЕЛ
    С ИСПОЛЬЗОВАНИЕМ МЕТОДА
    КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ] // ВЕСТНИК. — 2013. — № 4. — С. 30—31. Архивировано 22 декабря 2017 года.
  25. ↑ В.А. Минаев, Н.П. Васильев, В.В. Лукьянов, С.А. Никонов, Д.В. Никеров. [http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf ИНДЕКСНЫЕ АЛГОРИТМЫ
    ВЫЧИСЛЕНИЯ ПРОСТЫХ ЧИСЕЛ
    С ИСПОЛЬЗОВАНИЕМ МЕТОДА
    КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ] // ВЕСТНИК. — 2013. — № 4. — С. 30—33. Архивировано 22 декабря 2017 года.
  26. ↑ Jonathan Sorenson. An Analysis of Two Prime Number Sieves // Computer Sciences Department University of Wisconsin-Madison. — С. 16—18.
  27. ↑ Jonathan Sorenson. An Analysis of Two Prime Number Sieves // Computer Sciences Department University of Wisconsin-Madison. — С. 16.
  28. ↑ 1 2 3 Jonathan Sorenson. An Analysis of Two Prime Number Sieves // Computer Sciences Department University of Wisconsin-Madison. — С. 17.

Литература[править | править код]

  • Эратосфеново решето // Элоквенция — Яя. — М. : Советская энциклопедия, 1957. — С. 141. — (Большая советская энциклопедия : [в 51 т.] / гл. ред. Б. А. Введенский ; 1949—1958, т. 49).
  • Гальперин Г. «Просто о простых числах» // Квант. — 1987. — № 4. — С. 10-14,38.
  • Неопубликованные материалы Л.Эйлера по теории чисел / РАН, Институт истории естествознания и техники, С.-Петерб. фил.; Сост. Матвиевская Г.П. [и др.]; Отв. ред. Невская Н.И. — СПб.: Наука, 1997. — ISBN 5-02-024847-9.
  • Проф. Д.Ф.Егоров. Элементы теории чисел. — Государственное издательство Москва, 1923. (недоступная ссылка)
  • Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.

Ссылки[править | править код]

  • Решето Эратосфена от М. Гарднера
  • Алгоритм составления таблицы простых чисел от заданного до другого числа
  • Реализация алгоритма поиска простых чисел на Java
  • Доказательство сложности алгоритма
  • Еще раз о поиске простых чисел
Источник

Содержание материала

  1. Что такое простые числа
  2. Видео
  3. Разложение на простые множители
  4. Алгоритм разложения на простые множители
  5. Решение
  6. Разные свойства простых чисел*
  7. Метод Марена Мерсенна
  8. Быстрое возведение в степень
  9. Скатерть Улама
  10. Решето Эратосфена
  11. Как определить простые числа
  12. Темы для размышлений

Что такое простые числа

Определение 1

Простые числа — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.

Пример 1

Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом.

13 ÷ 4 = 3 (остаток 1).

Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.

Пример 2

30 не является примером простого числа, потому что его можно разделить на 1,2,3,5,6,10,15,30. Таким образом, 30 является примером составного числа, поскольку оно имеет более двух факторов.

Ноль, единица и числа меньше единицы не считаются простыми числами.

Видео

Разложение на простые множители

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

[11 = 11 = 11^1] [100 = 2 times 2 times 5 times 5 = 2^2 times 5^2] [126 = 2 times 3 times 3 times 7 = 2^1 times 3^2 times 7^1]

Рассмотрим, например, такую задачу:

Условие: Нужно разбить (N) людей на группы равного размера. Нам интересно, какие размеры это могут быть.

Решение: По сути нас просят найти число делителей (N). Нужно посмотреть на разложение числа (N) на простые множители, в общем виде оно выглядит так:

[N= p_1^{a_1} times p_2^{a_2} times ldots times p_k^{a_k}]

Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень (i)-го простого число от 0 до (a_i) (то есть (a_i+1) различное значение), и так для каждого. То есть делитель (N) выглядит ровно так: [M= p_1^{b_1} times p_2^{b_2} times ldots times p_k^{b_k}, 0 leq b_i leq a_i] Значит, ответом будет произведение ((a_1+1) times (a_2+1) times ldots times (a_k + 1)).

Алгоритм разложения на простые множители

Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа (N), мы можем число (N) на него поделить и продолжить искать новый минимальный простой делитель.

Будем перебирать простой делитель от (2) до корня из (N) (как и раньше), но в случае, если (N) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ((N) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда (N) стало либо (1), либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само (N) добавить в ответ.

Напишем алгоритм факторизации:

Решение

За те же самые (O(sqrt{N})). Итераций цикла while с перебором делителя будет не больше, чем (sqrt{N}). Причем ровно (sqrt{N}) операций будет только в том случае, если (N) — простое.

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

Разные свойства простых чисел*

Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:

  • Простых чисел, меньших (N), примерно (frac{N}{ln N}).
  • N-ое простое число равно примерно (Nln N).
  • Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
  • Для любого (N ge 2) на интервале ((N, 2N)) всегда найдется простое число (Постулат Бертрана)
  • Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с (N! + 2).
  • Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
  • Максимальное число делителей равно примерно (O(sqrt[3]{n})). Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
  • Максимальное число делителей у числа на отрезке ([1, 10^5]) — 128
  • Максимальное число делителей у числа на отрекзке ([1, 10^9]) — 1344
  • Максимальное число делителей у числа на отрезке ([1, 10^{18}]) — 103680
  • Наука умеет факторизовать числа за (O(sqrt[4]{n})), но об этом как-нибудь в другой раз.
  • Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.

Метод Марена Мерсенна

Метод простого числа Мерсенна — это специальный метод нахождения определенного вида простого числа, известный как простые числа Мерсенна. Название для этого метода происходит от французского монаха Марин Мерсенн, который первым определил его. Простые числа Мерсенна — это те, которые сводимы к виду 2n-1, где n-простое число. Первые несколько чисел в этом методе являются 2, 3, 5, 7, 13, 17, 19, 31, 61, и 89. Долгое время метод простых чисел Мерсенна представлял собой тяжёлую работу, так как при переходе к более высоким простым числам он был очень трудоемким.

Марен Мерсенн Французский математик

Марен Мерсенн Французский математик

Однако, с появлением компьютеров, они теперь могли выполнять эти вычислительные вычисления, которые раньше делались людьми самым кропотливым и трудоемким образом. Мы определенно достигли более высоких простых чисел Мерсенна и простых чисел на общем уровне. Поиск простых чисел так же активен, как и другие численные поиски, выполняемые компьютерами. Другой числовой поиск, аналогичный движению простых чисел, заключается в добавлении десятичных разрядов к некоторым иррациональным числам, таким как пи (отношение длины окружности к диаметру). Однако непрерывный поиск следующего по величине простого числа существенно сложнее, чем поиск следующей цифры числа Пи.

Даже самые большие компьютеры (суперкомпьютеры) тратят значительное количество времени, чтобы проверить, является ли новое число (которое обычно ошеломляюще огромным) само по себе простым числом, и требуется еще больше времени, чтобы проверить, является ли число основным числом Мерсенна. По этой причине числа Мерсенна представляют большой интерес в области кибербезопасности и криптографии, особенно в отношении шифрования.

В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!

Быстрое возведение в степень

Задача: > Даны натуральные числа (a, b, c < 10^9). Найдите (a^b) (mod (c)).

Мы хотим научиться возводить число в большую степень быстро, не просто умножая (a) на себя (b) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.

Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):

  • (3^2)
  • (3^4)
  • (3^8)
  • (3^{16})
  • (3^{32})
  • (3^{33})
  • (3^{66})
  • (3^{132})
  • (3^{133})
  • (3^{266})
  • (3^{532})
  • (3^{533})
  • (3^{1066})

Да, здесь специально приведена такая последовательность, в которой каждое следующее число легко считается через предыдущее: его либо нужно умножить на (a=3), либо возвести в квадрат. Так и получается рекурсивный алгоритм:

  • (a^0 = 1)
  • (a^{2k}=(a^{k})^2)
  • (a^{2k+1}=a^{2k}times a)

Нужно только после каждой операции делать mod: * (a^0 pmod c = 1) * (a^{2k} pmod c = (a^{k} pmod c)^2 pmod c) * (a^{2k+1} pmod c = ((a^{2k}pmod c) times a) pmod c)

Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)

Асимптотика этого алгоритма, очевидно, (O(log c)) — за каждые две итерации число уменьшается хотя бы в 2 раза.

Скатерть Улама

Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.

Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.

Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный многочлен x задаёт бесконечно много простых чисел, более того, все простые числа, но это неинтересный случай. А что можно сказать о многочлене ax+b (где a, b и x — натуральные числа)? Ясно, что если a и b имеют общий делитель, отличный от 1, то значение многочлена ax+b — число составное, кратное этому делителю. Случай же, когда a и b взаимно просты, гораздо менее очевиден.

Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что если a и b взаимно просты, то в арифметической прогрессии с первым членом b и разностью a встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в XIX столетии немецким математиком Леженом Дирихле.

Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен x2 + x + 41 — его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при x = 1, 2, …, 40. При x = 41 его значение — составное.

Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.

Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама 5. Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль какой-либо диагонали в пределах, ограниченных на рис. 1 красными линиями — это значения некоторого квадратного многочлена с целыми коэффициентами).

197 196 195 194 193 192 191 190 189 188 187 186 185 184 183
198 145 144 143 142 141 140 139 138 137 136 135 134 133 182
199 146 101 100 99 98 97 96 95 94 93 92 91 132 181
200 147 102 65 64 63 62 61 60 59 58 57 90 131 180
201 148 103 66 37 36 35 34 33 32 31 56 89 130 179
202 149 104 67 38 17 16 15 14 13 30 55 88 129 178
203 150 105 68 39 18 5 4 3 12 29 54 87 128 177
204 151 106 69 40 19 6 1 2 11 28 53 86 127 176
205 152 107 70 41 20 7 8 9 10 27 52 85 126 175
206 153 108 71 42 21 22 23 24 25 26 51 84 125 174
207 154 109 72 43 44 45 46 47 48 49 50 83 124 173
208 155 110 73 74 75 76 77 78 79 80 81 82 123 172
209 156 111 112 113 114 115 116 117 118 119 120 121 122 171
210 157 158 159 160 161 162 163 164 165 166 167 168 169 170
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225

Рис. 1.

Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел — на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название «скатерть Улама».

Рис. 2.

Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена x2 + x + 41 выстраиваются по диагоналям у спирали, начинающейся с числа 41 (рис. 3).

57 56 55 54 53
58 45 44 43 52
59 46 41 42 51
60 47 48 49 50
61 62 63 64 65

Рис. 3.

Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.

Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил какого-либо математического объяснения.

О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.

Решето Эратосфена

Это алгоритм поиска простых чисел. Для этого нужно:

  1. Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
  2. Вычеркнуть все числа, которые делятся на 2 (кроме 2);
  3. Вычеркнуть все числа, которые делятся на 3 (кроме 3);
  4. И так далее по порядку со всеми невычеркнутыми числами до числа n (после 3 это 5, 7, 11, 13, 17 и т. д.).

Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.

Как определить простые числа

Сначала попробуйте разделить его на 2 и посмотреть, получится ли целое число. Если да, то оно не может быть простым числом. Если вы не получите целое число, затем попробуйте разделить его на простые числа: 3, 5, 7, 11 (9 делится на 3) и так далее, всегда делясь на простое число.

8 простых чисел до 20: 2, 3, 5, 7, 11, 13, 17 и 19.

Первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Таблица простых чисел до 1000:

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 101 103 107 109
113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199 211 223 227
229 233 239 241 251 257 263 269 271 277
281 283 293 307 311 313 317 331 337 347
349 353 359 367 373 379 383 389 397 401
409 419 421 431 433 439 443 449 457 461
463 467 479 487 491 499 503 509 521 523
541 547 557 563 569 571 577 587 593 599
601 607 613 617 619 631 641 643 647 653
659 661 673 677 683 691 701 709 719 727
733 739 743 751 757 761 769 773 787 797
809 811 821 823 827 829 839 853 857 859
863 877 881 883 887 907 911 919 929 937
941 947 953 967 971 977 983 991 997

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

Примечание 

Один из самых известных математиков классической эпохи, Евклид, записал доказательство того, что не существует самого большого простого числа. Самое большое известное простое число (по состоянию на ноябрь 2020 года) составляет 282 589 933-1, число, которое имеет 24 862 048 цифр при записи в базе 10. До этого самым большим известным простым числом было 277 232 917-1, состоящее из 23 249 425 цифр.

За исключением 2 и 3, все остальные простые числа могут быть выражены в общей форме как 6n + 1 или 6n — 1, где n — натуральное число.

Чтобы определить, является ли число простым или составным, нужно решить пример на делимость в следующем порядке (от простого к сложному): 2, 5, 3, 11, 7, и 13. Если вы обнаружите, что число делится на одно из них, и вы знаете, что оно составное, не нужно выполнять остальные тесты.

Если число меньше 121 не делится на 2, 3, 5 или 7, оно простое; в противном случае оно составное.

Если число меньше 289 не делится на 2, 3, 5, 7, 11, или 13, это простое число; в противном случае оно составное.

Темы для размышлений

1.

Докажите, что в арифметических прогрессиях 3, 7, 11, … и 5, 11, 17, … бесконечно много простых чисел.
2.

Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль (см. рис. 1)

• начата с 1?

• начата с некоторого числа u?

• начата с некоторого числа u, и по спирали стоят члены арифметической прогрессии u, u + v, u + 2v, …?
3.

Теорема Вильсона утверждает, что если p — простое число, то (p–1)! + 1 делится на p. Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальном многочлене R, задающем простые числа?
4.

Постройте экспоненциальный многочлен S(x, …, xk ), который задаёт множество полусумм простых чисел-близнецов, т.е. такой многочлен, что если S(x, …, xk ) > 0, то оба числа S(x, …, xk ) – 1 и S(x, …, xk ) + 1 являются простыми, и наоборот, если s – 1 и s + 1 — простые числа, то S(x, …, xk ) = s при некоторых x, …, xk .
5.

Постройте экспоненциальный многочлен T(q, x, …, xm ), такой, что

• если q — простое число, то существуют числа x, …, xm  такие, что T(q, x, …, xm ) > 0;

• если q — простое число и T(q, x, …, xm ) > 0, то T(q, x, …, xm ) — простое число, следующее за q;

• если q не является простым числом, то всегда T(q, x, …, xm ) ≤ 0.

Этот экспоненциальный многочлен даёт «формулу для следующего простого числа».

Теги

Источник

Добавить комментарий