Определение взаимной простоты двух натуральных чисел

Определение взаимной простоты двух натуральных чисел

Введение

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

1.       Теоретические основы разработки

Чисел теория, наука о целых числах. Понятие целого числа, а также арифметических операций над числами известно с древних времён и является одной из первых математических абстракций.

Особое место среди целых чисел, то есть чисел..., -3, -2, -1, 0, 1, 2, 3,..., занимают натуральные числа - целые положительные числа 1, 2, 3,...- их свойства и операции над ними. Все натуральные числа, большие единицы, распадаются на 2 класса: к 1-му классу относятся числа, имеющие ровно два натуральных делителя, именно единицу и самого себя, ко 2-му - все остальные. Числа 1-го класса стали называть простыми, а 2-го - составными. Свойства простых чисел и их связь со всеми натуральными числами изучались Евклидом (3 в. до н. э.). Если выписывать простые числа подряд, то можно заметить, что относительная плотность их убывает: на первый десяток их приходится 4, т. е. 40%, на сотню - 25, т. е. 25%, на тысячу - 168, т. е. " 17%, на миллион - 78 498, т. е. " 8%, и т.д., однако их бесконечно много (Евклид).

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

Евклид считал очевидным, что с помощью умножения только простых чисел можно получить все натуральные числа, причём каждое натуральное число представимо в виде произведения простых чисел единственным образом (с точностью до порядка множителей). Т. о., простые числа образуют мультипликативный базис натурального ряда. Первыми задачами о простых числах были такие: как часто они расположены в натуральном ряде и как далеко они отстоят друг от друга. Изучение распределения простых чисел привело к созданию алгоритма (правила), позволяющего получать таблицы простых чисел. Таким алгоритмом является Эратосфена решето (3 в. до н. э.). Евклид в "Началах" указал способ нахождения общего наибольшего делителя двух чисел (Евклида алгоритм), следствием которого является теорема об однозначном разложении натуральных чисел на простые сомножители.

Множество всех целых чисел обычно обозначают буквой Z и понимают под ним набор всех действительных чисел без дробной части: {... , -3, -2, -1, 0, 1, 2, 3, ...}. Натуральные числа являются подмножеством целых чисел и образуют множество N: {1, 2, 3, ...}.

Простым числом называют натуральное число, большее единицы, которое делится только на 1 и на само себя. Все остальные числа называют составными. Первые 10 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Перечислим несколько свойств простых чисел:

• любое составное число представляется уникальным образом в виде произведения простых чисел; иначе еще говорят, что разложение числа на простые множители однозначно.

• простых чисел бесконечно много, причем существует примерно n/ln(n) простых чисел, меньших числа n.

• наименьший простой делитель составного числа n не превышает sqrt(n), поэтому для проверки простоты числа достаточно проверить его делимость на 2 и все нечетные (а еще лучше простые) числа, не превосходящие sqrt(n).

• любое четное число, большее двух представимо в виде суммы двух простых чисел; а любое нечетное, большее чем 5 представимо в виде суммы трех простых чисел

• для любого натурального n, большего единицы существует хотя бы одно простое число на интервале (n, 2*n)

Числа Мерсена - это числа, представимые в виде 2n-1. Особый интерес представляют простые числа Мерсена, которые получаются при n=2, 3, 5, 7, 13, 17, 19, 41, 47, 61, 89, 10, 127, ...

На сегодняшний день известно 44 простых числа Мерсена и самое большое из них получается при n=32582657 и содержит в себе почти 10 миллионов цифр, оно же является самым большим из найденных на сегодняшний день. Это же число является наибольшим среди всех известных простых чисел. На сегодняшний день неизвестно: конечно ли число простых чисел Мерсена.

Числа Ферма - это числа, представимые в виде 2n+1. Простыми среди чисел вида 2n+1 могут быть только числа Ферма. На данный момент известно всего 5 простых чисел Ферма: 3, 5, 17, 257, 65537; так же известно, что для 5≤n≤32 все числа Ферма - составные.

Совершенное число - это натуральное число, равное сумме всех своих делителей, не включая самого себя. Например, число 28 - совершенное число, т.к. 28=1+2+4+7+14. Вот первые 10 совершенных чисел: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176,

.

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

Дружественные числа - два натуральных числа, для которых сумма всех делителей первого числа (кроме него самого) равна второму числу и сумма всех делителей второго числа (кроме него самого) равна первому числу. Иногда частным случаем дружественных чисел считаются совершенные числа: каждое совершенное число дружественно себе. Обычно же, говоря о дружественных числах, имеют в виду пары из двух разных чисел. Первые 8

пар таких чисел: 220 и 284, 1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368, 10744 и 10856, 12285 и 14595, 17296 и 18416.

Число Армстронга - натуральное число, которое равно сумме своих цифр, возведённых в степень, равную количеству его цифр. Например, 1634 = 14 + 64 + 34 + 44. Последовательность чисел Армстронга начинается так: 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650,

... самовлюбленное число - натуральное число, которое равно сумме своих цифр, возведённых в степень m, где m - некоторое натуральное число. Числа Армстронга - частный случай таких чисел.

Число Смита - такое составное число, сумма цифр которого (в данной системе счисления) равняется сумме цифр всех его простых сомножителей. Так, примером числа Смита может служить 202, поскольку 2 + 0 + 2 = 4, и 2 + 1 + 0 + 1 = 4 (202 = 2 * 101). У. Л. МакДэниел доказал, что существует бесконечно много чисел Смита. Насчитывается 29928 чисел Смита в пределах до 1 000 000.

Первые 50 чисел Смита: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086.

1 Алгоритм Евклида для целых чисел

Наибольший общий делитель (НОД) двух целых чисел а и b - это наибольшее целое число, которое делит нацело оба числа. Далее мы будем рассматривать лишь неотрицательные числа, но это не влияет на общность рассуждений.

Пусть a и b (a > b) - целые числа, не равные одновременно нулю, и последовательность чисел: a>b>r1>r2>r3>…>rn определена следующим образом (рекуррентное соотношение):

a = bq0 + r1= r1q1 + r2= r2q2 + r3

……………− 2 = rn − 1qk − 1 + rn− 1 = rnqn

Тогда наибольший общий делитель a и b (НОД(a,b)), равен последнему ненулевому члену rn этой последовательности.

Существование таких r1, r2,..., то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих утверждений:

Пусть a = bq + r, тогда НОД(a,b) = НОД(b,r).

Доказательство:

Пусть k - любой общий делитель чисел a и b, не обязательно максимальный, тогда a = t1·k; b = t2·k; где t1 и t2 - целые числа из определения. Тогда k также общий делитель чисел b и r, так как b делится на k, а r = a − bq = (t1 − t2·q)·k (выражение в скобках есть целое число, следовательно, k делит r без остатка).

Обратное также верно и доказывается аналогично, то есть любой делитель b и r так же является делителем a и b.

Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a и b, который не был бы также делителем b и r, и наоборот. В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.

НОД(0,r) = r для любого ненулевого r.

Существует другой способ вычисления НОД(a,b) (процедура последовательного взаимного вычитания). Если даны натуральные числа a и b, то по очереди вычитается из большего числа меньшее до тех пор, пока получается положительное число. В результате получаем НОД(a,b):

если a ≠ b то

если a>b то a=a-b иначе b=b-a

всё=a

Отметим следующие свойства НОД (n>k):

1. НОД(2n, 2k) = 2 НОД(n, k).

2. НОД(2n, 2k+1) = НОД(n, 2k+1).

3. НОД(2n+1, 2k+1) = НОД(2n-2k, 2k+1) = НОД(n-k, 2k+1).

1 Анализ методов решения

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

2 Обзор средств программирования

Для решения практической части работы необходимо выбрать язык программирования. Как правило, это следующие алгоритмические языки программирования: Pascal, Basic, C. Интегрированные среды на основе этих языков позволяют работать с различными типами данных, массивами, типизированными переменными и выполнять разнообразные вычисления.

3 Описание выбранного языка программирования

Для решения поставленной задачи будем использовать объектно-ориентированный язык программирования Delphi-3. Этот язык позволяет работать с математическими формулами, проводить различного рода математические операции и действия. Он является расширением стандарта языка программирования Pascal, а также содержит интегрированную среду, ускоряющую и облегчающую процесс разработки программ. В объектно-ориентированном языке программирования Delphi-3 используется стандартные объекты, позволяющие работать как с обычными переменными, так и с типизированными массивами и строками, что открывает дополнительные возможности при решении математических задач. В математических задачах часто требуется реализовывать численные методы, экспериментально исследовать условие и скорость сходимости методов вычислений.

2. Практическая часть

1 Постановка задачи и разработка алгоритма решения задачи

Технико-математическая формулировка задачи

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

А) Оба числа (от 1 до 1 млрд.) вводятся с клавиатуры.

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

В) Расчет выполняется для каждой пары чисел, хранящихся в файле (числа от 1 до1 млрд.).

Г) По выбору пользователя каждое из чисел вводится либо с клавиатуры, либо из файла; диапазон чисел от 1 до 1 млрд; если числа вводятся из файла, то проверяется каждая пара чисел; например, если одно число вводится из файла-А.tхt, а второе - из В.tхt, то надо проверить на взаимную простоту сочетание каждого числа из одного файла с каждым числом из другого файла.

Описание исходных данных

Исходными данными являются 2 целых числа из диапазона от 1 до 1 млрд.

А) Оба числа вводятся с клавиатуры.

Б) Одно из чисел вводится с клавиатуры, другое число вводиться из отдельного файла (каждое число записывается с новой строки).

В) Оба числа вводятся из файла. В каждой строке файла по два числа, разделенных одним или несколькими пробелами.

Г) По выбору пользователя каждое из чисел вводится либо с клавиатуры, либо из отдельного файла (каждое число записывается с новой строки).

Требования к функциональным характеристикам

·   определение являются ли два числа взаимно простыми;

Требования к составу и форме выдачи результатов программы

Вывод результатов по желанию пользователя - на экран, принтер или в файл.

Ответ выводиться в одной из двух форм:

Числа <цццццццццц> и <цццццццццц> являются взаимно простыми.

Числа <цццццццццц> и <цццццццццц> не являются взаимно простыми.

Если выводится несколько пар чисел, то формат вывода изменяется.

1 Описание схем

В результате работы данной процедуры m примет значение НОД(n, m).

1 Текст программы

программа алгоритм простой число

1 Описание программы

Таблица идентификаторов

1 Руководство оператора

Программа имеет следующий интерфейс (Рис.1):

Рис.1

Интерфейс программы:

·   окно для ввода первого числа a;

·   окно для ввода второго числа b.

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

·   кнопка «OK» предназначена для обработки двух чисел, которые вписываются непосредственно в окна «a» и «b» или заносятся в те же окна из файлов a.txt и b.txt (соответствующими кнопками);

·   кнопка «Yes» предназначена для обработки двух чисел, разделённых одним пробелом, которые загружаются из файла INPUT.txt (открывается окно диалога) и сохраняет результаты в файле OUTPUT.txt (открывается окно диалога для сохранения файла);

·   кнопка «All» предназначена для обработки массива чисел, которые записаны в файл парами в каждой строке и разделёны одним пробелом (порядок открытия файлов такой же, как в предыдущем пункте).

1 Программа и методика испытаний

Тестирование алгоритмов и программ - одна из наиболее сложных и ответственных задач в процессе их отладки и спешка в работе недопустима. Проверка корректности алгоритмов и составление достаточно полного набора корректных тестов вовсе непростая задача.

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

2 Протокол испытания

При определении взаимной простоты чисел с помощью алгоритма Евклида получены следующие результаты:

1. Ввод данных в поля a и b (кнопка «OK»):

·   a=17, b=19 - nod(17,19)=1-взаимно просты (Рис.2);

·   a=1000000000, b=555555555 - nod(1000000000,55555555)=5-не взаимно просты (Рис.3).

Рис.2

Рис.3

1. Ввод данных из файла INPUT.txt (два числа разделены одним пробелом) - кнопка «Yes»:

·   a=1000000000, b=555555555 - nod(1000000000,55555555)=5-не взаимно просты (Рис.4).

Рис.4

1. Ввод данных из файла INPUT.txt (массив пар чисел, разделенных одним пробелом) - кнопка «All» (Рис.5):

Рис.5

Для просмотра результатов в окне ListBox надо воспользоваться прокруткой или открыть файл OUTPUT.txt (Рис.6).

Рис.5

Заключение

В ходе выполнения курсовой работы решены все поставленные задачи:

·   разобрана теоретическая часть (алгоритм Евклида);

·   разработана программа для проведения необходимых вычислений.