Пример: прости числа

В следващата задача се изисква да направим проверка за просто число. Преди да продължим към нея, нека си припомним какво са простите числа.

Определение: едно цяло число е просто, ако се дели без остатък единствено на себе си и на 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. Помислете защо.

results matching ""

    No results matching ""