Programming-Basics-Book-CSharp-BG
Пример: прости числа
В следващата задача се изисква да направим проверка за просто число. Преди да продължим към нея, нека си припомним какво са простите числа.
Определение: едно цяло число е просто, ако се дели без остатък единствено на себе си и на 1. По дефиниция простите числа са положителни и по-големи от 1. Най-малкото просто число е 2.
Можем да приемем, че цяло число n е просто, ако n > 1 и n не се дели на число между 2 и n-1.
Първите няколко прости числа са: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, …
За разлика от тях, непростите (композитни) числа са такива числа, чиято композиция е съставена от произведение на прости числа.
Ето няколко примерни непрости числа:
- 10 = 2 * 5
- 42 = 2 * 3 * 7
- 143 = 13 * 11
Алгоритъм за проверка дали дадено цяло число е просто: проверяваме дали n > 1 и n се дели на 2, 3, …, n-1 без остатък.
- Ако се раздели на някое от числата, значи е композитно.
- Ако не се раздели на никое от числата, значи е просто.
 |
Можем да оптимизираме алгоритъма, като вместо проверката да е до n-1, да се проверяват делителите до √n. Помислете защо. |