ck (Sender: TObject) ;, B, X: integer;:=12; B:=9; :=GCD (A, B); X=1 then Form1.Caption:= Ні НСД! Raquo; else Form1.Caption:= НСД= + IntToStr (X) ;;
5. Прості числа
Натуральне число p, більше одиниці, називається простим, якщо воно ділиться без остачі тільки на 1 і на себе. Основна теорема арифметики свідчить, що будь-яке натуральне число n, більше одиниці, може бути розкладено на витвір простих чисел, причому це розкладання єдине з точністю до порядку простих співмножників. Канонічне розкладання натурального числа n має вигляд:, де: p1 lt; p2 lt; ... lt; pk - різні прості числа,.
Завдання перевірки простоти натурального числа і завдання побудови великих простих чисел мають важливі програми в криптографії.
Елементарні методи перевірки простоти чисел
Нехай n N. Як перевірити, чи є n простим?
Метод пробних поділів
Якщо n - складене число, то n=ab, де: 1 lt; a b, причому.
Тому для d=2, 3, ..., перевіряємо, чи ділиться n на d? Якщо, дільник числа n не буде знайдений, то n - просте число. В іншому випадку буде знайдений мінімальний простий дільник числа n, тобто ми навіть розкладемо n на два множники.
Можливі модифікації цього методу. Наприклад, ми можемо перевірити, чи ділиться n на 2 і на 3, і якщо ні, то перебираємо далі тільки числа d види: 1 + 6j і 5+ 6j де, j=1, 2, ...
Решето Ератосфена
Якщо необхідно скласти таблицю всіх простих чисел в діапазоні чисел 2, 3, ..., N, то потрібно на початку викреслити всі числа, що діляться на 2, крім 2. Потім взяти число 3 і викреслити всі наступні числа, що діляться на 3. Потім взяти наступне, що не викреслене число (т. е. 5) і викреслити всі наступні діляться на нього числа, і так далі.
У підсумку залишаться лише прості числа.
Для роботи використовувала компонент Mеmo і командну кнопку Button, в обробнику події OnClick якій реалізується обчислення (Мал. 5).
Рис. 5
Текст програми, яка демонструє створення таблиці простих чисел в діапазоні 2 - 255.
procedure TForm1.Button1Click (Sender: TObject); N=255; NP=set of 2..N;:NP;, K, L: integer; .Clear;.Lines.Add ( Laquo; Прості числа менші N ,: );:=[2..N]; :=Trunc (sqrt (N + 1));:=1; K lt;=L do//Виконувати цикл до K lt;=LK:=K + 1 until K in simple;.Lines.Add (IntToStr (K)); i:=2 to N div K do simple:=simple - [K * i]; ; K:=L + 2 to N do K in simple then Memo1.Lines.Add (intToStr (K)) ;;
Тест на основі малої теореми Ферма
Для перевірки простоти чисел n порядку метод пробних поділів вже непридатний. Наступний тест заснований на малій теоремі Ферма: якщо n просте, то для будь-якого a Z виконано порівняння:
якщо ж при цьому (a, n)=1, то:
Тому для перевірки простоти n необхідно вибрати яке-небудь a Z і перевірити виконання малої теореми Ферма за log n арифметичних операцій (за допомогою бінарного зведення в ступінь в кільці Z/nZ). Якщо мала теорема Ферма не виконано, то n є складовим числом.
Якщо ж умови виконані, то попередньо можна зробити висновок про простоту n, оскільки теорема дає лише необхідна умова. Цей тест є ефективним для виявлення складених чисел.
Наприклад, для 100-значних чисел n види:, де перевірялося виконання тесту, і перші десять чисел, що пройшли цей тест, виявилися згодом простими.
Однак існують такі великі числа, звані числами Кармайкла, для яких умови тесту Ферма виконуються, тим не менше, ці числа є складовими. Найменшим числом Кармайкла є число 561, яке утворюється твором простих чисел 561=3 * 11 * 17. Для виявлення таких чисел є спеціальні алгоритми, засновані на теоремах Лагранжа, Еллера і ряду інших математиків.
Сучасні методи
Нижче наведений приклад, наочно демонструє процедуру генерування простих позитивних чисел в обраному діапазоні значень для типу Integer.
У прикладі використовувала компоненти SpinEdit 1,2 (для вибору значень діапазону чисел), компонент Memo - для відображення результатів і командну кнопку Button.
Рис. 6. Розташування елементів у формі
Функція перевірки на простоту числа
Так, як функція не декларується в розділах декларування те, тіло функції розташувала в Unit'e вище тіла команди тесту.
Simple (n: integer): Boolean; k: Boolean; i: integer;:=true; n lt; gt; 2 theni:=2 to trunc (sqrt (n)) + 1 don mod i=0 then:=false ;;;:=k ;;
Команда тесту функції
TForm1.Button1Click (Sender: TObject) ;: integer; .Clear; i:=SpinEdit1.Value to SpinEdit2.Value doSimple (i)=true then Memo1.Lines.Add (IntToStr (i) ) ;;
. Генератор псевдо випадкової послідо...
