МЕТОДЫ НАХОЖДЕНИЯ ПРОСТОГО ЧИСЛА, МЕТОДЫ РЕШЕТА

Муниципальное автономное  общеобразовательное учреждение «Средняя общеобразовательная школа г.Зеленоградска»

Проектная работа

На тему:  МЕТОДЫ НАХОЖДЕНИЯ ПРОСТОГО ЧИСЛА, МЕТОДЫ РЕШЕТА.

Выполнил:

Ученик 11 А класса

Поперняк Олег Анатольевич

Руководитель:

Учитель информатики

Ануфриева Евгения Андреевна

г. Зеленоградск

2018 год.

ВВЕДЕНИЕ

Цель моей работы исследовать применение простых чисел в жизни человека.

Для изучения этого вопроса, были поставлены следующие задачи

1. Дать определение простому числу.
2. Понять принцип выделения простых чисел из натурального ряда методами решета.
3. Составить листинги программ реализации методов на языке программирования Си++.
4. Сравнить эффективность работы алгоритмов Аткина и Эратосфена.

Для решения поставленных задач я использовал:

1. научную литературу: Гальперин Г. «Просто о простых числах», Чандрасекхаран К. «Введение в аналитическую теорию чисел», Трост Э. «Простые числа», Дэвенпорт Г. «Мультипликативная теория чисел».
2. Учебное пособие: Математика. 6 класс: учеб. Для общеобразоват. Учреждений/ Н.Я. Виленкин, В.И. Жохов, А.С. Чеснаков, С.И. Шварцбурд
3. Интернет ресурсы.

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

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

Вне математики основные способы применения простых чисел связаны с компьютерами. Компьютеры хранят все данные в виде последовательности нулей и единиц, которая может быть выражена целым числом. Многие компьютерные программы перемножают числа, привязанные к данным. Это означает, что под самой поверхностью лежат простые числа. Когда человек совершает любые онлайн-покупки, он пользуется тем, что есть способы умножения чисел, которые сложно расшифровать хакеру, но легко покупателю. Это работает за счет того, что простые числа не имеют особенных характеристик — в противном случае злоумышленник мог бы получить данные банковской карты.

В данной работе мы сравним методы решета Эратосфена и Аткина. Проверим эффективность данных алгоритмов.

1. Определение простого числа

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

 Простые числа - это, как известно еще из курса элементарной арифметики, те натуральные числа, которые делятся без остатка только на единицу и самое себя.

Кстати, если натуральное число делится, кроме выше перечисленных, еще на какое-либо число, то оно именуется составным. Одна из самых знаменитых теорем гласит, что любое составное число может быть представлено в виде единственно возможного произведения простых чисел. Несколько любопытных фактов. Во-первых, единица является уникальной в том плане, что, по сути, не принадлежит ни к простым, ни к составным числам. В то же время в научной среде все же принято относить ее именно к первой группе, так как формально она полностью удовлетворяет ее требованиям. Во-вторых, единственным четным числом, затесавшимся в группу «простые числа» является, естественно, двойка. Любое другое четное число сюда попасть попросту не может, так как уже по определению, кроме себя и единицы, делится еще и на два. Простые числа, список которых, как было указано выше, можно начинать с единицы, представляют собой бесконечный ряд, такой же бесконечный, как и ряд натуральных чисел. Опираясь на основную теорему арифметики, можно прийти к выводу, что простые числа никогда не прерываются и никогда не заканчиваются, так как в противном случае неизбежно прервался бы и ряд натуральных чисел. Простые числа не появляются в натуральном ряду беспорядочно, как это может показаться на первый взгляд. Внимательно проанализировав их, можно сразу заметить несколько особенностей, наиболее любопытные из которых связаны с так называемыми числами-«близнецами». Называют их так потому, что каким-то непостижимым образом они оказались по соседству друг с другом, разделенные только четным разграничителем (пять и семь, семнадцать и девятнадцать). Если внимательно к ним присмотреться, то можно заметить, что сумма этих чисел всегда кратна трем. Более того, при делении на тройку левого собрата в остатке всегда остается двойка, а правого – единица. Кроме того, само распределение этих чисел по натуральному ряду можно спрогнозировать, если представить весь этот ряд в виде колебательных синусоид, основные точки которых образуются при делении чисел на три и два. Простые числа являются не только объектом пристального рассмотрения со стороны математиков всего мира, но уже давно и успешно используются в составлении различных рядов чисел, что является основой, в том числе, для шифрографии. При этом следует признать, что огромное количество загадок, связанных с этими замечательными элементами, все еще ждут своих разгадок, многие вопросы имеют не только философское, но и практичное значение

2. Решето Эратосфена.

1. Алгоритм.

Решето Эратосфена – алгоритм нахождения всех простых чисел до некоторого целого числа n.Он был создан древнегреческим математиком Эратосфеном.

Для нахождения всех простых чисел не больше заданного числа n, выполним следующие шаги:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум — первому простому числу.
3. Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
4. Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
6. Все не вычеркнутые числа в списке — простые числа.

1.  Псевдокод.

Вход: натуральное число n

Пусть A — булевый массив, индексируемый числами от 2 до n, изначально заполненный значением true.

для i = 2, 3, 4, ..., пока i^2 ≤ n:

если A[i] = true:

для j = i^2, i^2 + i, i^2 + 2i, ..., пока j ≤ n:

A[j] = false

Теперь все числа i, такие что A[i] = true, являются простыми.

2. Пример для  n = 20.

Запишем натуральные числа начиная от 2 до 20 в ряд:

2   3   4   5   6   7   8   9   10   11   12   13

14   15   16   17   18   19   20

Первое число в списке 2 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 (каждое второе, начиная с 22 = 4):

2   3   4   5   6   7   8   9   10   11   12   13

14   15   16   17   18  19   20

Следующее невычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 32 = 9):

2   3   4   5   6   7   8   9   10   11   12   13

14   15   16   17   18   19   20

Следующее невычеркнутое число 5 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 52 = 25). И т. д.

Необходимо провести вычёркивания кратных для всех простых чисел p, для которых . В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.

3. Решето Аткина.

Решето Аткина – это быстрый современный алгоритм  нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм, то есть представление чисел в виде

3. Алгоритм.

1. Все числа, равные (по модулю 60) 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, или 58, делятся на два и заведомо не простые.

Все числа, равные  3, 9, 15, 21, 27, 33, 39, 45, 51, или 57, делятся на три и тоже не являются простыми.

Все числа, равные  5, 25, 35, или 55, делятся на пять и также не простые.

Все эти остатки игнорируются.

2. Все числа, равные (по модулю 60) 1, 13, 17, 29, 37, 41, 49 или 53, имеют остаток от деления на 4 равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения

нечётно и само число не кратно никакому квадрату простого числа.

3. Числа, равные (по модулю 60) 7, 19, 31, или 43, имеют остаток от деления на 6 равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения  нечётно и само число не кратно никакому квадрату простого.
4. Числа, равные (по модулю 60) 11, 23, 47, или 59, имеют остаток от деления на 12 равный 11. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения  нечётно и само число не кратно никакому квадрату простого.

Ни одно из рассматриваемых чисел не делится на 2, 3, или 5, соответственно, они не могут делиться и на их квадраты. Поэтому проверка, что число не кратно квадрату простого числа, не включает , , и .

4.  Предпросеивание.

Для ускорения работы полная версия алгоритма игнорирует все числа, которые кратны одному из нескольких первых простых чисел (2, 3, 5, 7, …). Это делается путем использования стандартных структур данных и алгоритмов их обработки, предложенных ранее Полом Притчардом. Они известны под названием wheel sieving. Количество первых простых чисел выбирается в зависимости от заданного числа N. Теоретически предлагается брать первые простые примерно до . Это позволяет улучшить асимптотическую оценку скорости алгоритма на множитель . При этом требуется дополнительная память, которая с ростом N ограничена как .

4. Неразрешенные загадки тысячелетия

Зная некие закономерности распределения простых чисел в натуральном ряду или некую гипотетическую формулу, связывающие число А с ее простыми делителями, злоумышленнику не пришлось бы с таким трудом раскладывать число А. Можно было бы просто воспользоваться этой формулой. Вот здесь мы и подошли к пониманию сути проблемы простых чисел – НЕТ 100% ДОКАЗАННЫХ ФОРМУЛ И ЗАКОНОМЕРНОСТЕЙ ОПИСЫВАЮЩИХ РАСПРЕДЕЛЕНИЕ ПРОСТЫХ ЧИСЕЛ В БЕСКОНЕЧНОМ НАТУРАЛЬНОМ РЯДУ!!!

Проблема отсутствия закономерностей распределения простых чисел занимает умы человечества еще со времен древнегреческих математиков. Благодаря Евклиду мы знаем, что простых чисел бесконечно много. Эрастофен, Сундарам предложили первые алгоритмы тестирования чисел на простоту. Эйлер, Ферма, Лежандр и многие другие известные математики пытались и пытаются по сей день разгадать загадку простых чисел. На сегодняшний момент найдено и предложено множество изящных алгоритмов, закономерностей, но все они применимы лишь для конечного ряда простых чисел или простых чисел специального вида. Передним же краем науки в исследованиях простых чисел на бесконечности считается доказательство гипотезы Римана. Она входит в семерку неразрешенных проблем тысячелетия, за доказательство или опровержение которой математическим институтом Клэя предложена премия в 1.000.000 $.

Заключение.

Я узнал, что простые числа являются не только объектом пристального изучения математиками всего мира, но уже давно и успешно используются. Наиболее распространенным примером использования простых чисел является применение их в криптографии (шифровании данных). Самые безопасные и трудно дешифруемые методы криптографии основаны на применении простых чисел, имеющих в составе более трех сотен цифр.

А знание   открытых законов позволит создать качественно новые решения в следующих областях:

• Сверхзащищённая операционная система для банков и корпораций.
• Система борьбы с контрафактной продукцией и поддельными денежными знаками.
• Система дистанционной идентификации и борьбы с угонами автотранспорта.
• Система борьбы с распространением компьютерных вирусов.
• Компьютеры нового поколения на нелинейной системе счисления природы.
• Математико-биологическое обоснование теории гармонии восприятий.
• Математический аппарат для нано – технологий.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Гальперин Г. Просто о простых числах: Квант. — № 4. 
2. Математика. 6 класс: учеб. Для общеобразоват. Учреждений/ Н.Я. Виленкин, В.И. Жохов, А.С. Чеснаков, С.И. Шварцбурд. – 29-е изд., испр. – М.: Мнемозина, 2012.
3. Чандрасекхаран К. Введение в аналитическую теорию чисел: Издательство «Мир», М., 1974.-187с.
4. Трост Э. Простые числа: Гос. Издательство , М.,1959.-136 с.
5. Дэвенпорт Г. Мультипликативная теория чисел: Издательство «Наука», М., 1971.-199с.
6. http://www.numbernautics.ru
7. http://fb.ru
8. https://www.mersenne.org
9. http://moluch.ru
10.  http://crypto.hut2.ru

Приложение 1

Язык программирования Си++

Алфавит языка включает:

-    прописные и строчные латинские буквы, причем прописная и строчная буквы – это разные символы;
-    знак подчеркивания;
-    арабские цифры от 0 до 9;
-    специальные знаки:
-    " { } ,  |  [ ]  ( )  +   -   /   %   *  .  \  :  ‘  ?  <   =   >   !   &   #   ~   ;   ^
-    пробельные символы: пробел, символы табуляции, символы перехода на новую строку.
-    Из символов алфавита формируются лексемы языка:
-    идентификаторы;
-    ключевые (зарезервированные) слова;
-    знаки операций;
-    константы;
-    разделители (специальные знаки, пробельные символы).
Границы лексем определяются другими лексемами, такими, как разделители или знаки операций.

Идентификатор – это имя программного объекта ( имя переменной, имя функции, метка). В идентификаторе могут использоваться латинские буквы, цифры и знак подчеркивания. Прописные и строчные буквы различаются, например, sysop, SySoP и SYSOP – три различных имени. Первым символом идентификатора может быть буква или знак подчеркивания, но не цифра. Пробелы внутри имен не допускаются.
Для улучшения читаемости программы следует давать объектам осмысленные имена. Существует соглашение о правилах создания имен, называемое венгерской нотацией (поскольку предложил ее сотрудник компании Microsoft венгр по национальности), по которому каждое слово, составляющее идентификатор, начинается с прописной буквы, а вначале ставится префикс, соответствующий типу величины, например, iMaxLength, lpfnSetFirstDialog. Другая традиция – разделять слова, составляющие имя, знаками подчеркивания: max_length, number_of_galosh.
Длина идентификатора по стандарту языка не ограничена, но компиляторы и компоновщики налагают на нее ограничения. При выборе идентификатора необходимо иметь в виду следующее:
-    идентификатор не должен совпадать с ключевыми словами и именами используемых стандартных объектов языка;
-    не рекомендуется начинать идентификаторы с символа подчеркивания, поскольку они могут совпасть с именами системных функций или переменных;

Ключевые слова – это зарезервированные идентификаторы, которые имеют специальное значение для компилятора. Их можно использовать только в том смысле, в котором они определены.

Знак операции – это один или более символов, определяющих действие над операндами. Операндами называются объекты, на которые направлена операция. Например:

Здесь x и 5 операнды, + операция, а y – результат операции.
 Внутри знака операции пробелы не допускаются. Операции делятся на унарные (действия с одним операндом), бинарные (действия с двумя операндами) и тернарные(действия с тремя операндами). Один и тот же знак может интерпретироваться по-разному в зависимости от контекста. Все знаки операций за исключением [ ], ( ) и ? : представляют собой отдельные лексемы.

Константами называют неизменяемые величины. Константы бывают литеральными (литералами) и типизированными. Литеральные константы характеризуются только своей величиной и неадресуемы. Типизированные константы имеют адрес и величину. Литеральные константы различаются на целые, вещественные (с плавающей точкой), символьные и строковые константы. Компилятор, выделив литеральную константу в качестве лексемы, относит ее к одному из типов по ее внешнему виду.

Если требуется сформировать отрицательную целую или вещественную константу, то перед константой ставится знак унарной операции изменения знака (-), например: -218, -022, -0хЗС, -4.8, -0.1е4.
Вещественная константа в экспоненциальном формате представляется в виде мантиссы и порядка. Мантисса записывается слева от знака экспоненты (Е или е), порядок – справа от знака. Значение константы определяется как произведение мантиссы и возведенного в указанную в порядке степень числа 10. Пробелы внутри числа не допускаются, а для отделения целой части от дробной используется не запятая, а точка.
Символьные константы, состоящие из одного символа, занимают в памяти один байт и имеют стандартный тип char. Двухсимвольные константы занимают два байта и имеют тип int, при этом первый символ размещается в байте с меньшим адресом.
Последовательности символов, начинающиеся с обратной косой черты, называют управляющими, или escape-последовательностями. Символ обратной косой черты используется для представления:
-    кодов, не имеющих графического изображения (например, \а – звуковой сигнал, \n – перевод курсора в начало следующей строки);
-    символов апострофа ( ' ), обратной косой черты ( \ ), знака вопроса (?) и кавычки (");
-    любого символа с помощью его шестнадцатеричного или восьмеричного кода, например, \073, \0xF5. Числовое значение должно находиться в диапазоне от 0 до 255.
Управляющая последовательность интерпретируется как одиночный символ. Если непосредственно за обратной косой чертой следует символ, не предусмотренный табл. I.3 Приложения I, результат интерпретации не определен. Если в последовательности цифр встречается недопустимая, она считается концом цифрового кода.
Управляющие последовательности могут использоваться и в строковых константах, называемых иначе строковыми литералами. Например, если внутри строки требуется записать кавычку, ее предваряют косой чертой, по которой компилятор отличает ее от кавычки, ограничивающей строку:
"Издательский дом \"Питер\""
Все строковые литералы рассматриваются компилятором как различные объекты. Две одинаковые строки будут занимать две различные области памяти.
Длинную строковую константу можно разместить на нескольких строках, используя в качестве знака переноса обратную косую черту, за которой следует перевод строки. Эти символы игнорируются компилятором, а следующая строка воспринимается как продолжение предыдущей. Например, строка
"Никто не доволен своей \
 внешностью, но все довольны \
 своим умом"
полностью эквивалентна строке
"Никто не доволен своей внешностью, но все довольны своим умом".
Строковый литерал представляется массивом символов и в конец каждого строкового литерала компилятором добавляется нулевой символ, представляемый управляющей последовательностью \0. Поэтому длина строки всегда на единицу больше количества символов в ее записи.
 Пустая символьная константа недопустима.

Комментарии помогают при чтении программ. Их наличие в программе можно отнести к правилам хорошего тона программистов. В них можно сформулировать алгоритм функции, указать назначение переменных и пояснить, что выполняется в данной части программы. Комментарии не влияют на размер выполняемой программы. Компилятор удаляет их до генерации кода.
Комментарий либо начинается с двух символов  //  и заканчивается символом перехода на новую строку, либо заключается между символами-скобками /* и */. Примеры:

/ *
Простейшая консольная программа C++Builder.
Выводит на экран "Hello World" и ждет, пока
пользователь не нажмет какую-нибудь клавишу.
*/
getch();     //Ожидание нажатия клавиши.

 Пару символов, которая ограничивает комментарии обоих видов, нельзя разбивать пробелом. Внутри комментария можно использовать любые допустимые на данном компьютере символы, а не только символы из алфавита языка C++, поскольку компилятор комментарии игнорирует. Вложенные комментарии стандартом не допускаются, хотя в некоторых компиляторах разрешены.
Рекомендуется использовать для пояснений //, а скобки /*   */ применять для временного исключения блоков кода при отладке. 

Приложение 2

Реализация решета Эратосфена на языке программирования Си++

#include

#include

#include

using namespace std;

const int SQRT_MAXN = 100000; // корень из максимального значения N

const int S = 10000;

bool nprime[SQRT_MAXN];

bool bl[S];

int primes[SQRT_MAXN];

int cnt;

int main(int argc, char *argv[])

{

        int n;

   cout << "Enter a number (between 1 and 10000) and press ENTER: ";

        cin >> n;

        int nsqrt = (int)sqrt (static_cast(n));

        for (int i=2; i<=nsqrt; ++i)

                if (!nprime[i]) {

                        primes[cnt++] = i;

                        for (int j=i+i; j<=nsqrt; j+=i)

                                nprime[j] = true;

                }

         int result = 0;

        for (int k=0, maxk=n/S; k<=maxk; ++k) {

                memset (bl, 0, sizeof bl);

                int start = k * S;

                for (int i=0; i

                        for ( int j=max((start+primes[i]-1)/primes[i],2)*primes[i]-start;

                         j

                                bl[j] = true;

                if (k == 0)

                        bl[0] = bl[1] = true;

                for (int i=0; i

                        if (!bl[i])

                                ++result;

        }

        cout << "Total: " <<  result << endl;

   system("PAUSE");

   return EXIT_SUCCESS;

}

Реализация решета Аткина на языке программирования Си++

//убраны доп.проверки делимости на 3 и 5

#include

#include

#include

using namespace std;

int main(int argc, char *argv[])

{

      int limit = 1000;

      bool is_prime[1001];

      int x2, y2;

      int n;

      // Инициализация решета

      int sqr_lim = (int)sqrt( static_cast(limit) );

      for (int i = 0; i <= limit; i++) is_prime[i] = false;

      is_prime[2] = true;

      is_prime[3] = true;

      // Предположительно простые - это целые с нечетным числом

      // представлений в данных квадратных формах.

      // x2 и y2 - это квадраты i и j (оптимизация).

      x2 = 0;

      for (int i = 1; i <= sqr_lim; i++) {

          x2 += 2 * i - 1;

          y2 = 0;

          for (int j = 1; j <= sqr_lim; j++) {

              y2 += 2 * j - 1;

              n = 4 * x2 + y2;

              if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))

                  is_prime[n] = !is_prime[n];

            // n = 3 * x2 + y2;

              n -= x2; // Оптимизация

              if ((n <= limit) && (n % 12 == 7))

                  is_prime[n] = !is_prime[n];

             // n = 3 * x2 - y2;

              n -= 2 * y2; // Оптимизация

              if ((i > j) && (n <= limit) && (n % 12 == 11))

                  is_prime[n] = !is_prime[n];

          }

      }

      // Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].

      // (основной этап не может их отсеять)

      for (int i = 5; i <= sqr_lim; i++) {

          if (is_prime[i]) {

              n = i * i;

              for (int j = n; j <= limit; j += n) {

                  is_prime[j] = false;

              }

          }

      }

      // Вывод списка простых чисел в консоль.-------------------------------

      cout << "2, 3, 5";

      for (int i = 6; i <= limit; i++) {  

          if (is_prime[i])  {

             cout <<", "<< i;

          }

      }

      cout << endl;

    system("PAUSE");

    return EXIT_SUCCESS;

}

Приложение 3