Репетитор по математике и физике
ДРАЧЕВ Александр Яковлевич (г. Екатеринбург)


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

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

Натуральные числа, которые больше единицы и не являются простыми, называются составными. Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один натуральный делитель), простые числа (имеющие два натуральных делителя) и составные числа (имеющие больше двух натуральных делителей). Изучением свойств простых чисел занимается теория чисел. Как простых, так и составных чисел бесконечно много.

Ряд простых чисел

Введите Nmax (значение по умолчанию 500, не более 10000) и нажмите кнопку [ Построить последовательность ]

Nmax =  


Алгоритм отпределения простоты числа

Для построения ряда простых чисел (см. выше) используется самый простой алгоритм проверки числа на простоту.
Если число меньше 4, то оно простое. Если больше, то последовательно проверяется — делится ли число нацело на целые числа от 2 до целой части квадратного корня из проверяемого числа. Если не делится, то число простое.

Реализация алгоритма на javascript:

function is_prime(n) {
   // функция возвращает True, если число n простое
   var sost = false;
   if (n < 4) {
     return true
   } else {
     i = 2;
     sqn = Math.round(Math.sqrt(n) + 0.5);
     do {
       if (n % i == 0) sost = true;
       i += 1;
     } while (i < sqn);
     return ! sost;
   }
}


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

Наибольшее известное простое число

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в своё время Эйлер, найдя простое число 231 − 1 = 2 147 483 647.

Наибольшим известным простым числом по состоянию на январь 2019 года является число Мерсенна M82 589 933 = 282 589 933 − 1.
Оно содержит 24 862 048 десятичных цифр; в книге с записью этого числа было бы около девяти тысяч страниц. Его нашли 7 декабря 2018 года в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

[]

Рекомендуем посмотреть:
Решение квадратного уравнения      Задача о муравье на резиновой ленте
Решение системы линейных уравнений методом Гаусса      Задача на круги Эйлера
Простые числа      Число 142857     

H © 2017– Репетитор по математике ДРАЧЕВ А.Я   Тел.: 8 912 665-13-27
партнеры: ЭЛИТА ТРЭВЭЛ. Туристическая компания · ПРОМАВТ СИСТЕМ. Автоматизация производства · АРНИ СПОРТ. Профессиональные тренажеры и спортивное оборудование · БАЛЛОН-ТОРГ. Баллоны для газов · ГРУЗОПЕРЕВОЗКИ по городу и области · НОВА АГРО. Решения для цветоводства