Простые и составные числа

Всем хорошо известно, что

натуральное число называется простым, если оно делится только на 1 и на самое себя.

Но при решении задач удобнее применять какие-либо языковые переформулировки этого определения или другие Простые и составные числасвойства простых чисел, равносильных этому определению.

Например, число n является простым, если при любом его разложении на натуральные множители ровно один из этих множителей равен 1. При этом слово «ровно» мы вставили для того, чтобы избежать определенной языковой двойственности: без этого уточнения «одинокое» слово «одно» может восприниматься часто как «хотя бы одно». А тогда 1 оказалась бы простым числом. Об этих особенностях языка — и «обычного», и математического русского языка мы также далее будем говорить.

Естественно, число n не является простым, если оно может быть разложено на два множителя, каждый из которых отличен от 1, и именно этим утверждением пользуются при доказательстве того, что данное число является составным: его раскладывают на множители и обязательно доказывают, что оба эти множителя отличны от 1.

Можно сказать и иначе: число n не является простым, если оно может быть разложено на два множителя, каждый из которых отличен от n: если в разложении n=ab один из множителей не равен 1, то второй не равен n.

Еще одно свойство чисел:

число n просто тогда и только тогда, когда оно не имеет простых делителей, отличных от n.

Поэтому всякое составное число имеет такие делители, т.е. всякое составное число имеет хотя бы один простой делитель.

Понятие простого числа часто, в том числе и в школьном курсе, относят только к натуральным числам, что является далеко не всегда удобным при рассмотрении делимости в множестве целых чисел. Поэтому это понятие удобно распространить и на целые числа, считая, что целое число п является простым, если его модуль — простое натуральное число: например, простыми являются числа -5 и -17, а -4 простым не является.

Такое обобщение понятия простого числа связано с главным свойством — невозможностью разложить простое число на множители разумным образом, «по-настоящему»: ведь равенство n=n\times1 — это, как говорят в математике, тривиальное разложение — оно выполняется для всех n, так что из него нельзя извлечь никакой информации о данном числе n.

Установить, простым или составным является конкретное натуральное число, как вы знаете, не так просто, и этой задачей математики занимаются уже две с половиной тысячи лет. Со времен Древней Греции известен один прием, решето Эратосфена, с которым вы могли познакомиться еще в 5-м классе. Этот прием сильно усовершенствован в теории чисел, и на нем основаны некоторые алгоритмы построения простых чисел, использующиеся в современных компьютерах.

В то же время можно указать эффективный, всегда ведущий к цели прием решения этой задачи — если задано число n, то надо постепенно перебирать все меньшие его простые числа, которые могли бы быть его делителями, и если таковых не окажется, то данное число само простое. Ясно, что выяснить простоту даже сравнительно небольшого числа этим приемом достаточно трудно.

Этот прием можно упростить, сократив вычисления более чем вдвое, причем из очень простых соображений. Именно, если n=ab и а<b, то а2<аb<n, т.е. достаточно проверять только такие числа а — «кандидаты» в делители, — которые удовлетворяют неравенству а2<n, т.е. а<4n. Например, для установления, является ли число 2131 простым или составным, достаточно испытать простые числа 2, 3, 5, 7, ... , 43 и можно не проверять 47, 53, 59 и т.д. Но даже если вы знаете не только «детские» признаки делимости, но и признаки делимости на 7, 11 и 13, то испытывать остальные простые от 17 до 43, делить n на эти числа — занятие довольно скучное.

Также скучно и весьма не просто собирать данные о какой-то конкретной фирме, но сейчас вы можете значительно упростить этот процесс с помощью Консалт-Бюро ТАЛИСМАН, этот ресурс быстро вам предоставит необходимые данные оценив надежность компании и выявив фирмы-однодневки.

Поделиться в соц. сетях

Опубликовать в Facebook

Оцените материал:

1 Star2 Stars3 Stars4 Stars5 Stars (2 голосов, рейтинг: 5,00 с 5)
Loading...Loading...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>