простое число
Простое число - это натуральное число, большее 1, у которого нет положительных делителей, отличных от 1 и самого. Естественное число больше 1, не являющееся простым числом, называется составным числом. Например, 5 является простым, потому что 1 и 5 являются его единственными положительными целыми множителями, тогда как 6 является составным, потому что он имеет делители 2 и 3 в дополнение к 1 и 6. Основная теорема арифметики устанавливает центральную роль простых чисел в теории чисел : любое целое число больше 1 может быть выражено как произведение простых чисел, которое уникально с точностью до порядка. Единственность в этой теореме требует исключения 1 как простого, потому что можно включить произвольно много экземпляров 1 в любой факторизации, например, 3, 1 × 3, 1 × 1 × 3 и т. Д. Все допустимые факторизации 3. Свойство будучи простым, называется примитивностью. Простой, но медленный метод проверки примитивности заданного числа n известен как пробное деление. Он состоит в проверке, является ли n кратным целому числу от 2 до. Алгоритмы, намного более эффективные, чем пробное деление, были разработаны для проверки простоты больших чисел.