Проверка за делимост

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

Искаме да направим машина, която може да отговоря на един прост въпрос от тип да/не. При входни данни цяло число 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 конзолата и да накараш тази функция да работи. Ако не, можеш да продължиш към следващата стъпка, където има работеща версия, от която да започнеш. (Между другото възможно е да завършиш този урок без никакво програмиране).

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.