Поиск простых чисел

Министерство  образования и науки Российской Федерации

 

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И  РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

 

Кафедра телевидения и управления (ТУ)

 

 

 

 

 

 

 

 

Поиск простых чисел

 

 

 

 

 

 

 

Выполнил:

Студент гр. 131-1

_________ К.О.Баранская

«    »      ______   _  2011 г.

 

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

Р.И. Аширбакиев

«___» ___________ 2011 г.

 

 

 

 

 

 

 

 

 

Томск 2011

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И  РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

Кафедра телевидения и управления (ТУ)

 

 

 

 

 

 

 

 

 

УТВЕРЖДАЮ

Зав. Кафедрой ТУ

 

______________

«___» ___________ 2011 г.

 

 

 

 

ТЕМА №3

Поиск простых чисел

 

• Описание задачи
• Применение
• Рассмотреть алгоритм решета Эратосфена обычное и блочное.
• Реализовать обычный метод нахождения простых чисел и с использованием обычного решета Эратосфена.

 

Содержание

 

1.   Введение 4

2.   Описание задачи 5

3.   Применение 6

4.   Алгоритм решета Эратосфена обычное и блочное 7

5.   Нахождения простых чисел с использованием обычного метода и обычного решета Эратосфена 8

6.   Заключение 10

7.   Список использованной литературы 11

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение

 

Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными.

Последовательность  простых чисел начинается так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Описание задачи

 

Дан натуральный  ряд чисел от M до N. Нужно вывести на экран простые числа, находящиеся в данном промежутке.

Для этого  нужно:

Задать внешний  цикл – перебор чисел от M (при условии, что M не равно 1) до N, в нем сделать проверку, является ли число (текущая переменная) простым, предположить, что оно простое и задать внутренний цикл от 2 до текущей переменной. Во внутреннем цикле задать первое условие – есть остаток от деления переменной внешнего цикла на переменную внутреннего, если нет, то выйти из цикла. Во внешнем цикле создать второе условие – изменилось ли наше предположение, если нет, то значит текущая переменная внешнего цикла – простое число.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Применение

 

1. Криптография - для систем шифрования с открытым  ключом, где основным принципом  является задача разложения числа  на множители.

2. Могут быть  использованы при построении  генераторов псевдослучайных чисел  или хэш-функций (вихрь Мерсенна).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Алгоритм решета Эратосфена обычное и блочное

 

Решето Эратосфена - это алгоритм, позволяющий найти все простые числа в отрезке   за  операций.

 

Алгоритм решета Эратосфена обычное:

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

 

Алгоритм решета Эратосфена блочное:

1. Пусть   — константа, определяющая размер блока, тогда всего будет   блоков,  -ый блок ( ) содержит числа в отрезке  .
2. Обрабатывая блоки по очереди, т.е. для каждого  -го блока перебирая все простые (от   до  ) и выполняя ими просеивание только внутри текущего блока.

 

 

 

 

 

 

 

 

 

 

 

5. Нахождения простых чисел с использованием обычного метода и обычного решета Эратосфена

 

Обычный метод:

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int main ()

{

   int M;

   int N;

   cin>>M;

   cin>>N;

   int i;

   int j;

   for (i=M; i<=N; i++)

      {

         int P = i;

             bool prime = true;

             for (int j = 2; j < P; j++)

             {

                     if(P % j == 0)

                     {

                             prime = false;

                             break;

                     }

             }

             if (prime == true)

             {

                     cout << P << " ";

             }

      }

   system(" pause");

     return 0;

  }

 

 

 

 

 

 

 

 

Метод обычного решета Эратосфена:

#include <vector>

using namespace std;

int main ()

{

int n;

vector<char> prime (n+1, true);

prime[0] = prime[1] = false;

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

       if (prime[i])

               for (int j=i*i; j<=n; j+=i)

                       prime[j] = false;

system(" pause");

     return 0;

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Заключение

 

В данной курсовой работе были рассмотрены примеры  нахождения простых чисел в языке  программирования С++, был реализован обычный метод нахождения простых  чисел и метод «Решето Эратосфена», который является наиболее быстрым способом.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7. Список использованной литературы

 

1. Определение простого числа. http://ru.wikipedia.org/wiki/Простое_число/ (дата обращения: 24.11.2011).
2. Решето Эратосфена. http://e-maxx.ru/algo/eratosthenes_sieve/ (дата обращения: 24.11.2011).
3. Алгоритм решета Эратосфена. http://ru.wikipedia.org/wiki/Решето_Эратосфена/ (дата обращения: 25.11.2011).