Определение простоты числа

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

Основная теорема арифметики

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

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

Методы

Перебор делителей

Задача сводится к перебору всех возможных делителей числа n, а именно всех чисел от 2ух до n.

Pascal
function isPrime( x:integer ):boolean;
var i:integer;
begin
 for i:=2 to (x-1) do
   if ( (x mod i)=0 ) then isPrime := false;
 isPrime := true;
end;

Тест Ферма

Этот алгоритм позволяет определить, является ли число простым с помощью возведения числа в степень и получения остатка от деления. Данный метод основывается на теореме Ферма (Ферма был плодовитый математик и теорем у него было много). Однако прошу сразу обратить внимание на тот факт, что существуют псевдопростые числа, которые проходят данный тест. Чем больше "a" вы перепробуете, тем больше вероятность того, что число окажется простым. Хуже того, существуют такие числа, которые проходят все тесты, такие числа называются числами Кармайкла (пример: 561, 41041, 825265).

Если n — простое число, то оно удовлетворяет сравнению 
a^(n-1) ≡ 1 (mod n)

Тест Агравала — Каяла — Саксены

Вход. данные: integer n > 1.
if n = ab 
	for integers a > 0 and b > 1, число - составное.
Найдем наименьшее r sтакое что or(n) > log2(n).
If 1 < gcd(a,n) < n for some a ? r, число - составное.
If n ≤ r, число - составное.
	for a = 1 to  do
		if (X+a)n ≠ Xn+a (mod Xr ? 1,n), число - составное;
Число - прстое.
Здесь or(n) это показатель числа n по модулю r, log — двоичный логарифм и  — функция Эйлера для r.

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

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

Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту;
       r — количество раундов.
Вывод: составное, означает, что m является составным числом;
       вероятно простое, означает, что m с высокой вероятностью является простым числом.
Представить m ? 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.
цикл А: повторить r раз:
   Выбрать случайное целое число a в отрезке [2, m ? 2]
   x ← at mod m
   если x = 1 или x = m ? 1, то перейти на следующую итерацию цикла А
   цикл B: повторить s ? 1 раз
      x ← x2 mod m
      если x = 1, то вернуть составное
      если x = m ? 1, то перейти на следующую итерацию цикла А
   вернуть составное
вернуть вероятно простое

Простое решение

На уроках ИКТ обычно предлагается довольно простое решение, суть которого в бесконечном делении числа на простые множители.  Для этого нужно исследовать интервал от 2 до корня из n, где n - это искомое число. Для этого в цикле будем проверять остатки от деления. (подсказка: процедура для получения остатка от деления называется mod)

if (n mod i)=0 then is_simple:=1;

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

Сам цикл написать довольно просто:

for i:=1 to trunc(sqrt(n)) do begin {ТЕЛО_ЦИКЛА} end;

Вот что у нас получилось:

readln(n);
for i:=1 to trunc(sqrt(n)) do begin 
if (n mod i)=0 then 
begin
 is_simple:=1;break;
end;
                               end;
if (is_simple=1) then writeln(?Число простое?);

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 20.11.17)