Предыдущая страница реферата | 17  18  19  20  21  22  23  24  25  26  27

Если к = p – простое число, то теорема верна.

Если к – составное число, то к = к1 m1, тогда n = к1 (m1 m), n к1, к1 < к, что противоречит выбранному наименьшему значению. Это и доказывает теорему.

Достаточно часто в математике приходитс для числа а Î N выяснять, является оно простым или составным. Для решения подобных задач предложен способ, носящий название “решето Эратосфена…” или способа отсеивания чисел кратных 2,3,…,p,… .

Опишем этот способ.

Если даны числа натурального ряда: 1,2,3,4,5,…,n, то для установления какими они являются: простыми или составными, поступают так: вычеркивают 1,2 и каждое второе, ибо каждое второе начинается от 3, делится на 2, поэтому является составным. Затем повторяем эту процедуру для 3. 3 вычеркивается и каждое третье, ибо 6 – третье по счету за 3, делится на 3. названную процедуру повторяют до простого числа с не превосходящего . Оставшиеся числа являются простыми.

Такой алгоритм можно использовать и для установления чисел в промежутке от n1 до n2.

Опишем его спецификацию . Если надо установить какие числа в промежутке от n1 до n2 являются простыми, то поступим так:

выясним простое или составное является число n1:

Проверим его делимость на 2,3,5,…p ≤ . Если оно не делится на эти простые числа, то оно простое;

Если оно делится хотя бы на одно из этих чисел, то оно составное.

при выяснении простого числа n, одновременно поступаем так:

2.1 если n12, то вычеркивают его и каждый второй (как в первом случае); и переходим к (n1 + 1);

2.2 если n1 2, то к числу добавляем 1 и вычеркиваем n1 + 1 и любое второе за ним;

2.3 если было 2.1, то переходим к (n1 + 1) и проверяется делим его на 3, повторяем процедуру решета Эратосфена переходит к (n1 + 2);

2.4 Если было 2.2, то проверяют делимость на 3;

2.4.1. если n13, то проверяю решето Эратосфена и переходят следующему.

не вычеркнутому числу и исследуют его делимое на 5;

2.4.2. если n1 = 3q + r, то в зависимости от r = 1 или r = 2, добавляем 1 или 2 и

n1 + 1, n1 + 2.

И любое третье по счету и т.д.

2.5 Если n1 оказалось простым, то все не вычеркнутые числа тоже простые. Если n1 оказалось составным, а ni – простое, то все стоящие за ni числа остальные простые.

Скачали данный реферат: Пров, Кудяев, Azhikeljamov, Нямин, Фессалоникия, Malinin.
Последние просмотренные рефераты на тему: индия реферат, доклад африка, предмет курсовой работы, реферат памятники.





Предыдущая страница реферата | 17  18  19  20  21  22  23  24  25  26  27