Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСИТЕТ

НАДВІРНЯНСЬКИЙ КОЛЕДЖ НТУ

КУРСОВИЙ ПРОЕКТ

з дисципліни “Алгоритмізація та програмування”

на тему: «Арифметичний метод побудови великих простих чисел. Числа Мерсенна»

Студент Грицюк П. І.

Керівник викладач Ілько М. В.

НАДВІРНА 2015



Зміст

• Вступ
• 1. Теорія простих чисел
• 1.1 Роль простих чисел у математиці
• 2. Опис алгоритму
• 2.1 Опис програми і підпрограм
• 2.2 Опис стандартних процедур і функцій
• 3. Опис інтерфейсу
• 3.1 Результати роботи програми
• 3.2 Інструкція користувача
• 3.2 Вимоги до апаратного забезпечення
• Висновки
• Перелік використаних джерел
• Додатки


Вступ

Виникнення чисел у житті не випадковість. Важко уявити собі спілкування без використання чисел. Історія чисел захоплююча й загадкова. Людство встановило низку законів і закономірностей світу чисел. Без чудової науки про числа - математики - немислимо сьогодні минуле, ні майбутнє. А скільки ще нерозгаданого!

"Найдавніші з походження числа - натуральні. "Струмки" натуральних чисел, зливаючись, породжують безмежний океан речовинних різного роду особливих спеціальних чисел", так писав про числа Б.А.Кордемський у своїй книжці "Дивний світ чисел". Особливої актуальності набувають питання, присвячені вивченню арифметичних алгоритмів побудови простих чисел, а саме чисел Мерсенна. Моя робота заснована на аналізі доступних мені джерел: ресурси мережі Internet та наукова література з алгебри та теорії простих чисел.

Мета проекту полягає у вивченні властивостей простих чисел Мерсенна.

У відповідності до мети сформульовані наступні завдання роботи:

1. Вивчити властивості простих чисел Мерсенна.

2. Розглянути застосування простих чисел Мерсенна на практиці.

3. Навчитися вираховувати алгоритм побудови простих чисел Мерсенна на заданому проміжку.

Об'єкт: числа Мерсена.

Предметом дослідження є властивості чисел Мерсенна та їх обрахунок. Функція (2p )-1.

Основними методами дослідження чисел Мерсенна є вивчення та обробка літературних джерел, систематизація даних за видами простих чисел та їх властивостями. Структура курсового проекту: робота складається зі вступу, трьох розділів, висновків, переліку використаних джерел та додатку.



1. Теорія простих чисел

1.1 Роль простих чисел у математиці

Кожне натуральне число, більше одиниці, ділиться принаймні на два числа: на 1 і на саме себе. Якщо ні на яке інше ціле натуральне число воно не ділиться, то називається простим, а якщо у нього є ще якісь цілі дільники, то складеним. Не про всяке число можна одразу сказати, просте воно чи складене. Візьмемо, наприклад, число 1999. Якщо немає під рукою спеціальних довідкових таблиць або помічника - комп'ютера, то доведеться згадати про старе, але надійне решето Ератосфена. Старовинний спосіб, придуманий ще в ІІІ ст. до н. е. Ератосфеном Кіренським, зберігачем знаменитої Олександрійської бібліотеки.

Випишемо кілька чисел поспіль, починаючи з 2. Двійку відберемо в свою колекцію, а інші числа, кратні 2, закреслимо. Найближчим не закресленим числом буде 3. Візьмемо до колекції і його, а всі інші числа, кратні 3, закреслимо. При цьому виявиться, що деякі числа вже були викреслені раніше, як, наприклад, 6, 12 та інші. Наступне найменше не закреслено число - це 5. Беремо п'ятірку, а інші числа, кратні 5, перекреслюємо. Повторюючи цю процедуру знову і знову, ми врешті-решт досягнемо того, що не закресленими залишаться одні лише прості числа - вони немов просіяні крізь решето. Тому такий спосіб і отримав назву решето Ератосфена.

Однак спосіб Ератосфена не зміг задовольнити вчених, і вони намагалися знайти формулу простих чисел. Протягом багатьох століть це зробити не вдавалося. У ряду простих чисел було знайдено багато цікаві закономірності, але поставлена задача залишалася без відповіді.

Припустимо, що існує якесь найбільше просте число P. Тоді перемножимо всі прості числа, починаючи з 2 і закінчуючи P, і збільшимо отримане число на одиницю: 2 3 5 7 ... P + 1 = M. Якщо число М складене, то вона повинна мати принаймні один простий дільник. Але цим дільником не може бути ні одне з простих чисел 2, 3, 5, ..., Р, оскільки при розподілі М на кожне з них отримуємо в залишку 1. Отже, число М або просте, або ділиться на просте число, більше Р. Значить, припущення, що існує найбільше просте число Р, напевно й безліч простих чисел, нескінченне.

Першу відому нам таблицю простих чисел склав італійський математик П'єтро Антоніо Катальді в 1603 р. Вона захоплювала всі прості числа від 2 до 743.

У 1770 р. німецький математик Йоганн Генріх Ламберт опублікував таблицю найменших дільників всіх чисел, не переважаючих 102000, які не діляться на 2, 3, 5. Вклавши в цю працю воістину колосальні зусилля, Ламберт гарантував безсмертя тому, хто доведе таблицю дільників до мільйона. На його заклик відгукнулися багато обчислювачів.

До середини ХІХ століття вже були складені таблиці найменших дільників не тільки першого мільйона, а й наступних дев'яти. В цей же час в пресі з'явилися повідомлення, що подавалися абсолютно фантастичними: у Віденську академію надійшло 7 великих томів рукописних таблиць "Великий канон дільників всіх чисел, які не діляться на 2, 3 і 5, і простих чисел між ними до 100 330 201". Автором цієї праці був Якоб Філіп Кулик, професор вищої математики Празького університету.

У подальшому пошуку простих чисел вже не носили характеру масового полювання, з якою можна порівняти складання таблиць, а перетворилися на цілеспрямований відбір окремих представників. У мисливців за числами найбільш популярними є прості числа Мерсена. Вони названі на честь французького вченого Марена Мерсенна, що зіграв у XVIII ст. значну роль у становленні європейської науки.

Деякі уявлення про розподіл простих чисел мали вже стародавні греки. З доказів Евкліда випливає, наприклад, що вони не зібрані разом, а розкидані по всій числовій осі. У 1845 р. французький математик Жозеф Бертан, досліджуючи таблицю простих чисел у проміжку від 1 до 6000000, виявив, що між числами n і n² - 2, де n > 3, міститься принаймні одне просте число. Надалі ця властивість отримала назву постулати Бертрана, хоча самому Бертану обґрунтувати його так і не вдалося. Довів його в 1852 р. російський математик Пафнутій Львович Чебишев. З результату Чебишева випливала і більш точна оцінка. Таким чином, навіть серед дуже великих чисел прості числа не так вже й рідкісні.

З іншого боку, існують проміжки, що включають тисячі, мільйони, мільярди, і взагалі, яку завгодно велику кількість натуральних чисел, серед яких не можна знайти жодного простого. Справді, задавшись довільним великим натуральним числом к, побудуємо ряд чисел к! +2, К! +3, ..., К! + К (тут до! = 1 * 2 * 3 * ... * к). Кожне з цих чисел складене. Наприклад, число к! + М ділиться на м, оскільки до! ділиться на м і саме м ділиться на м.

Прості числа, що діляться тільки на одиницю і на самих себе (2,3,5,7,11,13,17, ...), з давніх часів привертають увагу математиків. Більше двох тисяч років тому великий давньогрецький математик Евклід довів, що ряд простих чисел нескінченний. Прості числа слідують одне за одним по закону, який ще не знайдений. Ці числа то на довго зникають з натурального ряду, то часто в ньому присутні, а іноді й по сусідству: 11,13; 5971847,5971849.

У 1750 р. Леонард Ейлер встановив, що число 2 і№ - 1 є простим. Воно залишалося найбільшим з відомих простих чисел більше ста років. У 1876 р. Французький математик Лукас встановив, що величезна кількість 2127 - 1=170 141 183 560 469 231 731 687 303 715 884 105727 також просте. Воно містить 39 цифр.

Для його обчислення були механічні настільні рахункові машини. У 1957 р. було знайдено наступне просте число: 23217 - 1. А просте число 244 497 - 1 складається з 13 000 цифр.



1.2 Прості числа Мерсенна, досконалі числа

Серед простих чисел особливу роль відіграють прості числа Мерсенна - числа виду 1) М_р = 2^р -1, де р - просте число. Вони називаються простими числами Мерсенна за іменем французького ченця Марена Мерсенна (1588-1648), одного із засновників Паризької академії наук, друга Декарта і Ферма. Так як М₂ = 3, М₃ = 7, М₅ = 31, М₇ = 127, то це - прості числа Мерсенна. Однак, число 2) М₁₁ = 2047 = 23Ч89 простим не є. До 1750 року було знайдено всього 8 простих чисел Мерсенна: М₂, М₃, М₅, М₇, М₁₃, М₁₇, М₁₉, М₃₁. Те, що М₃₁ - просте число, довів в 1750 році Л. Ейлер. У 1876 році французький математик Едуард Люк встановив, що число

3) М₁₂₇ = 170141183460469231731687303715884105727 - просте.

У 1883 р. сільський священик Пермської губернії І.М.Первушин без всяких обчислювальних приладів довів, що число М₆₁ = 2305843009213693951 є простим. Пізніше було встановлено, що числа М₈₉ і М₁₀₇ - прості. Використання ЕОМ дозволило в 1952-1964 роках довести, що числа М₅₂₁, М₆₀₇, М₁₂₇₉, М₂₂₀₃, М₂₂₈₁, М₃₂₁₇, М₄₂₅₃, М₄₄₂₃, М₂₆₈₉, М₉₉₄₁, М₁₁₂₁₃ - прості. До теперішнього часу відомо вже більше 30 простих чисел Мерсенна, одне з яких М₂₁₆₀₉₁ має 65050 цифр. Послідовність чисел Мерсенна починається так: 1, 3, 7, 15 , 31, 63, 127, 255, 511, 1023 , ...

Іноді числами Мерсенна називають числа M_p з простими індексами p . Ця послідовність починається так: 3, 7, 31 , 127, 2047 , 8191 , 131 071 , 524 287 , 8388607 , ...

Великий інтерес до простих чисел Мерсенна викликаний їх тісним зв'язком з досконалими числами.

Натуральне число Р називається досконалим, якщо воно дорівнює сумі всіх своїх дільників крім Р.

Евклід довів, що якщо р і 2^р-1 - прості числа, то число 4) Р_р = 2^р-1(2^р-1) = 2^р-1М_р є досконалим. Дійсно, дільниками такого числа, включаючи саме це число, є 1,2, ... , 2^р-1, М_р, 2М_р, ... , 2^р-1М_р.

Їх сума S_p = (1+2+ ... +2^р-1)(М_р+1) = (2^р-1) ^. 2^р = 2 ^. 2^р-1 М_р. Віднімаючи з S саме число Р_р, переконуємося, що сума всіх дільників числа Р_р дорівнює цьому числу, отже Р_р - досконале число.

Числа Р₂ = 6 і Р₃ = 28 були відомі ще піфагорійцям. Числа Р₅ = 496 і Р₇ = 8128 знайшов Евклід. Використовуючи інші прості числа Мерсенна і формулу, знаходимо такі досконалі числа: Р₁₃ = 33550336, Р₁₇ = 8589869056, Р₁₉ = 137438691328, Р₃₁ = 2305843008139952128.

Для всіх інших чисел Мерсенна числа Р_р мають дуже багато цифр.

Досі залишається загадкою, як Мерсенн зміг висловити правильне твердження, що числа Р_17, Р_19, Р₃₁ є досконалими. Пізніше було виявлено, що майже за сто років до Мерсенна числа Р_17, Р₁₉ знайшов італійський математик Катальді - професор університетів Флоренції і Болоньї. Вважалося, що божественне провидіння передбачило своїм обранцям правильні значення цих скоєних чисел. Якщо врахувати, що ще піфагорійці вважали першим досконале число 6 символом душі, що друге досконале число 28 відповідало числу членів багатьох вчених товариств, що навіть у ХІІ ст. церква вчила: для спасіння душі досить вивчати досконалі числа і тому, хто знайде нове божественне досконале число, уготовано вічне блаженство, то стає зрозумілим винятковий інтерес до цих чисел.

Однак і з математичної точки зору парні досконалі числа по-своєму унікальні. Всі вони - трикутні.

Сума величин, зворотних всім дільникам числа, включаючи саме число, завжди дорівнює двом. Залишок від ділення досконалого числа, крім 6, на 9 дорівнює 1. У двійковій системі досконале число Р_р починається р одиницями, потім слідують р-1 нулів, наприклад: 7) Р₂ = 110, Р₃ = 11100, Р₅ = 111110000, Р₇ = 1111111000000 і т.д.

Остання цифра парного досконалого числа або 6, або 8, причому, якщо 8, то їй передує 2.

Леонард Ейлер довів, що всі парні досконалі числа мають вигляд 2^р-1 ^. М_р, де М_р - просте число Мерсенна. Проте до цих пір не знайдено жодного непарного досконалого числа. Висловлено припущення (Брайен Такхерман, США), що якщо таке число існує, то воно повинно мати не менше 36 знаків.

1.3 Знаходження нового числа Мерсенна

Математик Кертіс Купер, учасник проекту GIMPS (Great Internet Mersenne Prime Search), виявив 48-е просте число Мерсенна. Десятковий запис такого числа складається з більш ніж 17 мільйонів знаків. Для порівняння, у «Війні і мирі» Толстого всього приблизно 3,1 мільйона символів. За своє відкриття професор Міссурського центрального університету цілком може отримати три тисячі доларів. Втім, він, як і інші учасники GIMPS, займається пошуком простих чисел Мерсенна зовсім не заради грошей.

Числа Мерсенна - це числа виду 2^p - 1, де p - довільне ціле число, яке називають показником. Ці числа вабили математиків з найдавніших часів, орієнтовно з Евкліда (приблизно 300 р. до н. е.), правда, до XVI ст. вчені вважали, що всі ці числа прості (тобто діляться тільки на себе і одиницю). Це, звичайно ж, неправильно - досить поглянути на четверте число Мерсенна: воно дорівнює 15 і зображається у вигляді добутку 3 і 5.

Мабуть, першим, хто помітив, що не всі числа Мерсенна з простими показниками (відомо, що для складових показників число Мерсенна не може бути простим) є простими, був Худальрікус Региус в 1536 році. Він показав, що при p = 11 отримане число - це 2047 - виявляється складеним, оскільки зображується у вигляді добутку 23 і 89.

Треба сказати, що перемозі над гіпотезою Мерсенна сприяла поява так званого тесту Люка-Лемера. Суть його полягає в наступному: для фіксованого числа Мерсенна обчислюється деяка рекурентна послідовність. Рекурентна формула для членів цієї послідовності, по-перше, відносно проста, а по-друге, для перевірки потрібно взяти p - 2 члени послідовності, де p - непарний простий показник числа Мерсенна. Складність роботи алгоритму складає близько третього ступеня log n, де n - саме число Мерсенна. Використання різного роду методів швидкого множення, як, наприклад, методу Шенхаге-Штрассена, дозволяє трохи прискорити роботу, проте кардинально складності не змінює.

Многочлен Джонса. Формула для генерації простих чисел: множина невід'ємних значень цього многочлена від 26 змінних, для всіляких наборів з 26 натуральних чисел дає всі прості числа.

Потрібно розуміти, що це вкрай низька обчислювальна складність, тобто алгоритм працює досить швидко. Для порівняння, найшвидший детерміністський алгоритм перевірки простоти з існуючих - тест Агравала-Каяла-Саксени з поліпшеннями Померанса-Ленстра - має складність порядку (log n)⁶. Відносну простоту програмування та низьку обчислювальну складність тесту Люка-Лемера вчені оцінили тільки з появою комп'ютерів.

У 60-ті роки минулого століття інтерес до чисел Мерсенна став спадати. Пов'язано це було з тим, що перспективи обчислювальної техніки на той момент бачилися досить туманними, а використання суперкомп'ютерів для пошуку великих простих чисел здавалося досить марнотратним. У 1968 році в університеті Іллінойсу було відкрито 23-е просте число Мерсенна з показником 11213. На той момент це було настільки великим досягненням, що Пол Бейтман, який керував кафедрою теорії чисел в цьому університеті, замовив спеціальну печатку для кореспонденції, на якій, крім дати, красувався напис «2¹¹²¹³ - 1 - просте число». У 1970-х роках інтерес до чисел Мерсенна знову активізувався. Причиною тому стала історія двох тоді ще американських школярів - Лаури Нікел і Лендона Нолла. Не особливо розбираючись в математичних тонкощах питання, вони написали програму для перевірки чисел Мерсенна на простоту за допомогою тесту Люка-Лемера і прогнали її на суперкомп'ютері в місцевому університеті. У результаті вони змогли знайти 25-е і 26-е прості числа Мерсенна з показниками 21 701 і 23 209 відповідно. Це були найбільші прості числа з відомих на той момент. Нолл після цього став володарем ще одного рекорду - в 1989 році він взяв участь у відкритті найбільшого простого числа, яке не є числом Мерсенна (це так зване просте число Амдала, назване так на честь робочої групи, яка відкрила його, і рівне 391581* 2²¹⁶¹⁹³-1).

Історія з відкриттям школярів потрапила на телеекрани, і пошук простих чисел Мерсенна знову повернувся в моду. Наступні успіхи у цій діяльності були пов'язані з суперкомп'ютерами Крей - один зі співробітників компанії-виробника Девід Словінскі написав програму для пошуку простих чисел Мерсенна, що працювала на цих машинах, поки вони не використовувалися. Нарешті, сучасний вигляд цей процес набув за допомогою програміста Джорджа Уолтмана, в 1995 році створив проект розподілених обчислень GIMPS (Great Internet Mersenne Prime Search).

Проект до кінця першого року існування налічував вже більше тисячі учасників. Це був перший дослідний проект розподілених обчислень в історії. Перше просте число Мерсенна (в даний час в рамках проекту їх відкрито вже 14) стало відомо в 1996 році. Зараз програму, що працює під усіма основними операційними системами, може встановити собі будь-який бажаючий. Сумарна обчислювальна потужність проекту до кінця 2012 року становила вже 95 терафлопс.

Найостаннішим відкриттям в проекті GIMPS стало виявлення 48-го простого числа Мерсенна. Це відкриття було зроблено математиком з Міссурського центрального університету Кертісом Купером. На прогонку тесту Люка-Лемера на одній з машин в університеті у Купера пішло 39 днів. Його результат був перевірений ще раз трьома незалежними користувачами, один з яких використовував 32-ядерний сервер, наданий компанією Новартіс. Розміри нового числа вражають - його запис у десятковій системі числення складається з 17425170 знаків. Для самого ж Кертіса це відкриття стало вже третім - раніше найбільші прості числа йому вдавалося виявляти в 2005 і 2006 роках.

У 2008-му рекорд Кертіса був побитий групою дослідників з Каліфорнійського університету в Лос-Анджелесі. Вони виявили просте число Мерсенна, в десяткового запису якого було 12978189 знаків. На момент відкриття це число було 45-м простим числом Мерсенна, проте через деякий час було відкрито ще два простих числа, менших цього (числа не завжди відкриваються у порядку зростання), тому його номер на даний час - 47. Саме воно до відкриття Купера було рекордсменом за розміром.

За відкриття GIMPS отримав премію в 100 тисяч доларів від фонду EFF, обіцяну за відкриття першого простого числа, записаного більш ніж 10 мільйонами знаків. Отримані гроші проект розділив на невеликі премії для заохочення наступних відкриттів - так, Купер з 48-м числом Мерсенна претендує на три тисячі доларів.

Примітно, що з числами Мерсенна пов'язана велика кількість досі невирішених завдань. Наприклад, поки невідомо, чи нескінченна множина простих чисел Мерсенна. На закінчення хочеться згадати ще про одну чудову властивість чисел Мерсенна. Число називається досконалим, якщо воно дорівнює сумі всіх своїх власних (тобто додатних і відмінних від самого числа) дільників, включаючи 1. Наприклад, 6 - досконале, оскільки 6 = 3 + 2 + 1. Ще Евклід виявив, що число виду 2^{n - 1} (2ⁿ - 1) досконале, якщо в дужках стоїть просте число, тобто просте число Мерсенна з показником n. Пізніше Леонард Ейлер довів, що всі парні досконалі числа мають такий вигляд, де в дужках стоїть просте число Мерсенна. На даний момент невідомо жодного непарного досконалого числа, проте існують припущення, що шукати такі числа також слід за допомогою чисел Мерсенна.



2. Опис алгоритму

2.1 Опис програми і підпрограм

В курсовому проекті мною була розроблена програма, яка здійснює аналіз та обрахунок простих чисел Мерсенна. Розглянемо детальніше цей метод та його програмну реалізацію.

Вона складається з головного меню та підпунктів. Об'єкти-пункти головного меню: «Головне меню» з вкладеними підпунктами «Курсовий проект» - виводить на екран таку інформацію: назву навчального закладу, тему курсового проекту та студента, який створив його; «Вивід чисел Мерсенна» - дозволяє виводити на екран монітора результат обрахунку простих чисел; «Вихід» - дозволяє вийти з програми. Підменю «Щоб продовжити, натисніть 1» з меню «Курсовий проект» дозволяє переходити до обрахунку простих чисел Мерсенна. Підменю «Щоб вийти в головне меню натисніть 2» з меню «Курсовий проект» повертає користувача в «Головне меню». Після обрахунку кожного простого числа Мерсенна виводиться на екран час, за який було обчислене кожне число.

простий число апаратний забезпечення



2.2 Опис стандартних процедур і функцій

При створенні програми для обрахунку простих чисел Мерсенна мною були використані стандартні функції, які описані в цьому розділі.

Функція setlocale дозволяє отримати або встановити деякі параметри, які залежать від геополітичного середовища виконання програми. Якщо показник locale є нулем, то функція setlocale () повертає показник на рядок поточної локалізації. Інакше функція setlocale () спробує використовувати рядок locale для установки локальних параметрів відповідно до параметру type. Функція printf() відповідає за вивід інформації на екран комп'ютера. Printf () є функцією стандартного виводу. За допомогою цієї функції можна вивести на екран монітора рядок символів, число, значення змінної і т.д. Функція printf () має прототип у файлі stdio.h int printf (char * керуючий рядок, ...).

У разі успіху функція printf () повертає число виведених символів.

Керуючий рядок містить два типи інформації: символи, які безпосередньо виводяться на екран, і специфікатори формату, що визначають як виводити аргументи.

Функція printf () - це функція форматованого виводу. Це означає, що в параметрах функції необхідно вказати формат даних, які будуть виводитися. Формат даних вказується специфікаторами формату. Специфікатор формату починається з символу «%» за яким слідує код формату.

Для виводу я використав такий специфікатор формату: printf("%s", LINE4);

printf("\n| Щоб вийти в головне меню натиснiть 2 | \n");

printf("%s", LINE4);

printf("\n| \t Щоб вийти натиснiть 3 | \n");

printf("%s", LINE4);

Функція system("cls") дозволяє стирати всю інформацію, яка виводилась попередньо. Функція if () повертає одне значення, якщо обчислене значення заданої умови - TRUE (правда), та інше значення, якщо обчислене значення заданої умови - FALSE (брехня). Наприклад, формула = IF(A1>10;"Більше 10";"10 або менше") повертає напис «Більше 10», якщо значення клітинки A1 більше 10, і «10 або менше», якщо значення клітинки A1 менше або дорівнює 10. Я використовував функцію if() таким чином:

if (key2 == 2)

{

goto L;

}

Функція time повертає поточне календарне значення часу в секундах. Якщо аргумент не є нульовим покажчиком, їй передається значення часу типу time_t.

Функція system виконує задану, через параметр syscom, системну команду. Насправді, функція не виконує команду, а викликає командний процесор для виконання команд. Після виконання команди, командний процесор повертає управління програмі, повертаючи цілочисельне значення, інтерпретація якого залежить від системи.

Оператор циклу while або цикл while - цикл, що повторює одну і ту ж дію, поки умова продовження циклу while залишається істинною.

Умова продовження циклу має бути істинно true (правда), як тільки умова стала хибною, виконується вихід з циклу. Також як і в умовних операторах вибору, фігурні дужки можуть опускатися в тому випадку, якщо тіло циклу - це один оператор. Але як правило в циклі виконується кілька операторів, так як крім виконання корисної дії необхідно робити умова циклу while хибним, інакше цикл буде нескінченним, а це, в свою чергу, призведе до зависання програми.

For. Якщо ми знаємо точну кількість дій (ітерацій) циклу, то можемо використовувати цикл for. Наприклад :

for (int i = 1; k < p; i = i ++){

<circles body>}

Оператор goto здійснює безумовну передачу управління, мітка якого задана ідентифікатором.



3. Опис інтерфейсу

3.1 Результати роботи програми

Програма передбачена для роботи в консольному режимі. Якщо вводиться користувачем функціональна клавіша не передбачена програмою, то вона виконуватися не буде до тих пір, поки користувач не введе зазначену клавішу, яка зазначена в інструкції для користувача. Виклик програми здійснюється шляхом запуску файлу Курсова.exe, при цьому програма буде працювати в інтерактивному режимі. Вікно допомоги програми містить: титульну сторінку, вікно для вирахування простих чисел Мерсенна, функціональні клавіші використовуються в програмі, при виводі чисел Мерсенна також виводить час у секундах, за який було вирахувано число.

3.2 Інструкція користувача

Приступаючи до роботи, користувач бачить перед собою головне меню, з нього за допомогою керуючих символів та натискання кнопки «Enter», можна переходити від одного меню до іншого підменю, повертатись в головне меню також можна із будь - якого підменю, кнопка «Вийти» дозволяє вийти із програми.

3.3 Вимоги до апаратного забезпечення

Дана програма призначена для вираховування простих чисел Мерсенна. Програма може працювати на IBM сумісних комп'ютерах сімейства х86 починаючи з 286 і вище, під управлінням операційних систем Ms-DOS 3.0 і вище для Windows 9x. Наявність .NETFramework Дану програму компілювали з використанням Visual Studio 2010.



Висновки

В ході роботи над курсовим проектом розглянуто та вивчено основні властивості чисел Мерсенна, проаналізовано доступні джерела, розглянуто деякі приклади застосування теорем, алгоритмів для пошуку чисел Мерсенна.

Основними властивостями простих чисел є:

· множина простих чисел нескінченна;

· будь-яке натуральне число більше 1 можна представити у вигляді добутку простих чисел і таке представлення є єдиним з точністю до порядку множників;

· якщо р - просте і аb ділиться на р, то а ділиться на р або b ділиться на р;

· будь-яке натуральне число n більше 1 ділиться хоча б на одне просте число;

· якщо р - просте число і якщо і відомо, що рn, n = p або n = -p.

Також ознайомився з властивостями чисел Мерсенна:

· будь-який дільник числа для простого p має вигляд 2pk + 1, де k - ціле число;

· кожне парне досконале число має вигляд , де число Мерсенна є простим.

Також не малопомітним було те, що прості числа мають багато цікавих властивостей. Наприклад, різниця деяких простих чисел дорівнює 2, тому вони будуть числами-близнятами. Прості числа становлять одну із найважливіших тем, яка повертає нас до самого початку математики, а потім, по мірі зростання важкості, приводять на край сучасної науки. Окрім того, що прості числа становлять з себе одну з найцікавіших тем математики, вони дуже корисні в нашому житті. На їхніх властивостях побудовані секретні коди, які захищають електронну пошту, банківські операції, кредитні картки і мобільний телефонний зв'язок.

Прості числа досліджували багато вчених-математиків, вони хотіли віднайти формулу, завдяки якої могли згенерувати прості числа, але жодному не вдалося. Можна сказати, що пошук простих чисел, пошук формули, щоб згенерувати їх як шкідливий вірус, якщо він захоплює розум математика, то його дуже важко викоренити. Історію простих чисел порівнюють з історією поразок і невдач, але прекрасних невдач, які привели до появи нових теорій, свіжих поглядів і передових рубежів.

Практичне й теоретичне значення: результати дослідження можуть бути використані студентами та викладачами, які цікавляться алгеброю та теорією чисел, зокрема при розв'язанні математичних задач та як основа для спецкурсів, а також в криптографії та системах захисту інформації.



Перелік використаних джерел

1. Алгебра и начала анализа: Учебн. для 10--11 кл. общ. учредж. / Под ред.А. Н. Колмогорова. -- 12-е изд.-- М.: Просвещение, 2002. -- 384 с.

2. Амелькин В. Задачи з параметром.:методичка -- Минск:Заря, 1994 - 234 с.

3. Вишенський В. А., Перестюк М. О., Самойленко А. М. Збірник задач з математики: Навч. посібник. -- 2-ге вид., доп. -- К.: Либідь, 1993. -- 344 с.

4. Гусак Г. М., Капуцкая Д. А. Математика для подготовительных отделений вузов: Справ. пособие / Под ред. А. А. Гусака. -- Мн.: Высш. шк., 1989. -- 495 с.

5. Лурьве М. В., Александров Б. И. Задачи на составление уравнений: Учеб. на составление уравнений: Учеб. рук-во. -- 3-е изд., перераб. -- М.: Наука, 1990. -- 96 с.

6. Маслай Г. С., Шоголева Л. О. Рівняння та системи рівнянь з параметрами: Математика. № 21--22 (81--82), Червень 2000.

7. Маслова Т. Н., Суходений А. М. Ваш домашний репетитор. -- М.: ООО «Изд. дом “ОНИКС 21 век”», 2003. -- 672 с.

8. Математика для поступающих в экономические вузы: Уч. пос. для вузов / Под ред. проф. Н. М. Кремера. -- 2-ге изд., перераб. и доп. -- М.: ЮНИТИ, 1998. -- 430 с.

9. Мордкович А. Г. Наибольшее и наименьше значения величин. -- М.: Школа-Пресс, 1995. -- 144 с.

10. Саушкін О. Ф. Розв'язування алгебраїчних рівнянь. -- К.: КНЕУ.

11. Чайковський В.Я. Квадратні рівняння. -- К., 1970. -- 242 с.



Додатки

Додаток А. Код програми

#include "stdafx.h"

#include <iostream>

#include <math.h>

#include <time.h>

#define LINE "|

#define LINE2

#define LINE3 "

#define LINE4 "

#define LINE5

using namespace std;

bool resheto(ch)

{

flag=true;

for (int i=2;i<ch-1;i++)

if (ch%i==0)flag=false;

return flag;

}

int main()

{

setlocale(0, "ukr");

{

int key, key2, L;

L:

cout << "" << endl;

cout << "|<><><><> Головне меню <><><><>|" << endl;

printf("%s", LINE);

printf("\n| 1. Курсовий проект. | \n");

printf("%s", LINE);

printf("\n| 2. Виведення чисел Мерсенна. | \n");

printf("%s", LINE);

printf("\n| 3. Вийти | \n");

printf("%s", LINE);

cout << endl;

cin >> key;

system("cls");

if (key == 3)

{

return 0;

}

if (key == 1)

{

cout << "" << endl;

cout << "|\t\t \t\t|" << endl;

printf("| НАЦIОНАЛЬНИЙ ТРАНСПОРТНИЙ УНIВЕРСИТЕТ \t| \n");

printf("|\t\t НАДВIРНЯНСЬКИЙ КОЛЕДЖ НТУ \t\t| \n");

cout << "| \t\t\t\t|" << endl;

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("|\t\t Завдання \t| \n");

printf("| \t\t\t\t| \n");

printf("|\t на курсовий проект студенту групи IТ - 21 | \n");

printf("| \t\t\t\t| \n");

printf("|\t\t Грицюк Петро Iгорович \t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| Арифметичнi алгоритми побудови великих простих чисел | \n");

printf("| \t\t\t\t| \n");

printf("|\t\t Числа Мерсенна \t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("| \t\t\t\t| \n");

printf("|\t Надвiрна 2015 \t| \n");

printf("%s", LINE2);

cout << "\n____________" << endl;

cout << "\n| \t Щоб продовжити, натиснiть 1 | \n";

printf("%s", LINE4);

printf("\n| Щоб вийти в головне меню натиснiть 2 | \n");

printf("%s", LINE4);

printf("\n| \t Щоб вийти натиснiть 3 | \n");

printf("%s", LINE4);

cin >> key2;

system("cls");

if (key2 == 3)

{

return 0;

}

if (key2 == 2)

{

goto L;

}

if (key2 == 1)

{L1:

int k, key;

time_t t1, t2;

float p, j;

printf("%s", LINE5);

cout << "\n| Вивiд скiлькох чисел ви бажаєте побачити (вiд 1 до 48) (p) :" ;

cin >> p;

cout << "|\t\t\t\t\t\t |" << endl;

k = 0;

t1 = time(0);

for (float i = 2; i < p; i = i + 1)

{

j = pow(2, i) - 1;

if(resheto(j))cout << "| Вiдповiдь M" << i << " : " << j << "\t\t\n";

t2 = time(0);

cout << "| Кiлькiсть секунд, затрачених на обрахунок : " << (t2-t1) << "\t \t |\n";

k++;

printf("%s \n", LINE5);

}

cout << "| Щоб вийти в головне меню натиснiть 2 |\n";

cout << "| Щоб вийти, натиснiть клавiшу 3 |\n";

cout << "| Щоб повторити натиснiть на клавiшу 4 |\n";

cout << "|___________________|\n";

cin >> key;

system("cls");

if (key == 4)

{

goto L1;

}

if (key == 3)

{

return 0;

}

if (key == 2)

{

goto L;

}

}

while (!key == 0);

}

if (key == 2)

{

goto L1;

}

if (key == 3)

return 0;

if (key == 2)

goto L;

}

system("pause>>void");

return 0;

}



Додаток В

Специфікатори формату

% с	символ
% d	ціле десяткове число
% i	ціле десяткове число
% e	десяткове число у вигляді x.xx e+xx
% E	десяткове число у вигляді x.xx E+xx
% f	десяткове число з плаваючою точкою xx.xxxx
% F	десяткове число з плаваючою точкою xx.xxxx
% g	% f або % e, виводить число з плаваючою точкою
% G	% F або % E, виводить число з плаваючою точкою
% o	вісімкове число
% s	рядок символів
% u	Без знакове десяткове число
% x	шістнадцяткове число
% X	шістнадцяткове число
% %	символ %
% p	вказівник
% n	вказівник

Крім того, до команд формату можуть бути застосовані модифікатори l та h.

% ld	вивід long int
% hu	вивід short unsigned
% Lf	вивід long double

Крім специфікаторів формату даних в керуючому рядку можуть перебувати керуючі символи:

\ b	BS, забой
\ f	Нова сторінка, перехід на нову сторінку
\ n	Новий рядок, перехід на новий рядок
\ r	Повертає каретку на попереднє місце
\ t	Горизонтальна табуляція
\ v	Вертикальна табуляція
\ "	Лапки
\ '	Апостроф
\ \	Зворотня коса лінія
\ 0	Нулевий символ, нулевий байт
\ a	Сигнал
\ N	Вісімкова константа
\ xN	Шіснадцяткова константа
\ ?	Знак питання

Размещено на Allbest.ru