Простые числа в программировании

/ 12 июля, 2020/ Mathematics, Programming/ 0 комментариев

numbers

Начнём с определения. Оно не является довольно сложным для восприятия, так что любой из нас может его себе представить в голове. Просто число (англ. prime number) – это такое натуральное число, которое имеет ровно 2 различных делителя – самого себя и единицу. Следовательно, если это условие не выполняется, то число является составным.

Принято считать, что 1 не относится ни к простым, ни к составным числа.

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

Теорема Вильсона:

«Натуральное число n>1 является простым тогда и только тогда, когда (n-1)!+1 делится нацело на n»

Опубликованная в 1782 году теорема является частным случаем малой теоремы Ферма, в которой также используются простые числа. Но, к сожалению, на практике данная теорема не применяется и носит чисто теоретический характер, так как вычисление факториала больших чисел является проблемой для программирования. Приведем примерный код программы на языке Java:

public static void main(String[] args) {
for(int i = 1;i<20;i++) {
if((factorial(i-1)+1)%i == 0) System.out.println(i);//проверка условия
    }
}

public static long factorial(int n) {
long rezult;
if (n == 0 || n == 1) return 1;
rezult = factorial(n-1)*n; //рекуррентная функция
return rezult;
}

В Java тип данных long позволяет правильно определить значение факториала от 0 до 20 включительно(большинство других языков программирования также позволяют вычислить также в промежутке от 0 до 20). Дальше пользоваться этим алгоритмом не представляется возможным, так как самому посчитать факториал чисел от 21 нереально, а из-за значений переменных программа будет работать некорректно.

 

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

История: Эратосфен Киренский (276 – 194 г. д. н. э) был выдающимся учёным в области математики, астрономии, географии и филологии. Нас, в первую очередь, интересуют его достижения в области математики, а именно – способ определения n-ного количества простых чисел.

Также, согласно легенде, этот метод получил такое название благодаря «своеобразному» способу поиска простых чисел: ученый записывал числа на дощечке, покрытой воском, и прокалывал отверстия в тех местах, где были написаны составные числа. Поэтому доска являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались лишь простые числа.

Суть этого метода заключается в том, чтобы «отсеять» значения элементов, которые делятся на какое-то текущее число из массива элементов.

Если описать алгоритм словесно, то он выглядит так:

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

Оставшиеся элементы и будут искомыми простыми числами.

Eratosphen

Примерный код на Java выглядит следующим образом:

class MyPrimeNum {
private boolean primes[];

public MyPrimeNum(int n){
   primes = new boolean[n+1];
}
public void fillNumbers() {
   Arrays.fill(primes, true);
   primes[0] = false;
   primes[1] = false;
   for (int i = 2; i < primes.length; i++) {
       if (primes[i]) {
            for (int j = 2; i * j < primes.length; j++) {
                 primes[i * j] = false;
            }
       }
   }
}
}

Числа Мерсенна

Это такие числа, которые представлены в виде формулы Mn = 2n – 1, где n – натуральное число.

Было доказано, что для чисел n, таких что n = kl, где n, k, l  > 0, число будет Mn  также составным (разложение 2kl – 1 на множители). Следовательно, если n будет простым, то и Mn также будут простыми. Рассмотрим это на примерах:

M2 = 22 – 1 = 3
M3 = 23 – 1 = 7
M4 = 24 – 1 = 15
M5 = 25 – 1 = 31
M6 = 26 – 1 = 63
M7 = 27 – 1 = 127
M8 = 28 – 1 = 255
M9 = 29 – 1 = 512
M10 = 210 – 1 = 1023
M11 = 211 – 1 = 2047

Как простые числа используются в программировании?

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

  • современных операционных систем
  • защищенных каналов сотовой связи
  • протоколов передачи данных Ethernet
  • протоколах передачи данных приватных компаний
Поделиться этой записью

Оставить комментарий