Дефиниране на проблема

Искаме да направим машина, която може да отговоря на един прост въпрос от тип да/не. При входни данни цяло число n, то дали n е просто число ли е?
Да помислим какво в тази машина ще я накара да работи. Машините могат само да следват последователност от стъпки, базирани на някакви инструкции, наречени алгоритъм. За да загреем, нека да разберем какво е алгоритъм в твоя мозък. Отговори на следния въпрос: Числото 49 просто ли е?
Не? Как го направи? Вероятно потърси делител на 49, който е по-голям от 1 и по-малък от 49. Ако не знаеш наизуст таблицата за умножение, вероятно следваш тази последователност:
  • Дали 2 дели 49?     НЕ
  • Дали 3 дели 49?     НЕ
  • Дали 4 дели 49?     НЕ
  • Дали 5 дели 49?     НЕ
  • Дали 6 дели 49?     НЕ
  • Дали 7 дели 49?    ДА
Намерихме делител на 49 (7), което е доказателство, че числото 49 е съставно.

Изграждане на стена

Ами ако въпросът беше дали 2971215073 е просто?
Все още ли проверяваш? След първите няколко хиляди теста все още нямам делител. Ключът към този въпрос е кога можем да спрем да проверяваме дали числото n е просто? (да го наречем нашата стена) Като отправна точка знаем, че нашата стена трябва да е n-1 (тъй като n дели n). Ако проверим до 2971215072, или ще намерим делител (което доказва, че n е съставно), ИЛИ няма да намерим (което доказва, че n е просто).

Изграждане на по-добра стена

Това върши работа, но можем ли да преместим стената, за да спестим време? Запомни, че търсим първия (или най-малък) делител. Понякога най-малкият делител може да е 2, но може да е много по-голямо число. Това ни води до ключовия въпрос: колко голям може да е най-малкият делител?
Запомни, че всяко съставно цяло число n се състои от две или повече прости числа n= P * P …
P е най-голямо, когато n има точно два делителя, които са равни един на друг. Това число е известно като квадрат като 9 (9 = 33) или 49 (49 = 77). За да уловим този най-лош случай, просто изграждаме нашата стена до корен квадратен от n!
Убеди себе си: ако не намерим делител на n, след като проверим до корен квадратен от n, то n трябва да бъде просто число. Опитай се да го докажеш на себе си (доказателството е в долната част на статията)

Алгоритъм за проверка за делимост

Това е, готови сме да продължим. Първо да обобщим нашия алгоритъм за проверка за делимост на прост език:
  • Като вход приемаме някакво цяло число n
  • За всяко цяло число x от {2 ... sqrt(n)} проверяваме дали x дели n
  • Ако намерим делител, то n е съставно число в противен случай n е просто число
Ако имаш опит с програмиране, можеш да отвориш CS конзолата и да накараш тази функция да работи. Ако не, можеш да продължиш към следващата стъпка, където има работеща версия, от която да започнеш. (Между другото възможно е да завършиш този урок без никакво програмиране).
Зареждане