Алгоритм решета [2]

1. Виписати поспіль всі цілі числа від двох до (2, 3, 4, ..., ).

2. Нехай змінна спочатку дорівнює - першому простому числу.

3. Викреслити зі списку всі числа від до , що діляться на (тобто, числа ...)

4. Знайти перше не викреслене число, більше ніж , і присвоїти значенню змінної p це число.

5. Повторювати кроки 3 та 4 до тих пір, поки менше ніж

6. Всі не викреслені числа у списку – прості.

Зображення даних в оперативній пам’яті [2]

Розв’язання задачі методом решета можна представити в оперативній пам’яті комп’ютера у вигляді масиву логічних зміних, які визначають чи задовільняє це число поставлену умову, а саме число буде номером елемента масиву.

Опис алгоритму програмного модуля [2]

Для "просіву" на решеті знаходиться перший елемент масиву з істинним значенням. На самому початку роботи програми цим елементом буде елемент з індексом 2. Далі виконується умова if і ми потрапляємо на внутрішній цикл for, який служить для перегляду іншої частини масиву. Значення кожного індексу, а числа у нас виражені в індексах, будуть перевірятися на наявність залишку від ділення на . Якщо число ділиться без залишку, значить, воно вже не може бути простим і значить, відповідно, false.

for(i= 2; i<N i++) //перевірка всіх чисел інтервалу

{

if(<число ще не викреслено>) // якщо елемент масиву true

{

for(int j = i*2; j < N; j++)

{

if(j% i== 0) //якщо ділиться націло

<присвоїти поточному елементу масиву значення false>

}

}

}

Оцінка складності алгоритму

Складність алгоритму складає операцій у моделі обчислень RAM, або бітових операцій.

Опис програми Методи та засоби розробки програми

Прикладні задачі даної розрахунково-графічної роботи реалізовано за допомогою високорівневої мови програмування C++ в середовищі Miscrosoft VisualStudio 2008, використано принцип модульності. Кожна прикладна задача була виконано в окремому cpp файлі.

Назва модуль	Призначення
salesman.cpp	Модуль, який реалізує задачу комівояжера
sieve.cpp	Модуль, який реалізує решето Ератосфена
prime.cpp	Модуль, який реалізує задачу пошуку простих чисел
bullscows.cpp	Модуль, який реалізує модифікацію задачі бики та корови
bullscows1.cpp	Модуль, який реалізує задачу про бики та корови
Main.cpp	Головний модуль для виведеня меню та вибору задачі

iomanip.h	Містить функції для форматованого виводу
iostream	Містить функції і змінні для організації вводу-виведення
conio.h	Містить функції для роботи з консольним вводом-введенням

Сценарій роботи програми

1. Користувач знаходиться в головному меню програми, зробленого за допомогою HTML. Йому доступні такі пункти меню:

• Головна

• Теоретичні відомості (опис методу)

• Прикладні задачі (список виконаних прикладних задач за даним алгоритмом)

• Відомості про виконавця.

2. При виборі пункту «Теоретичні відомості», користувачу буде доступна інформація з описом методів.

3. При виборі певної задачі з пункту «Прикладні задачі», користувачеві буде доступна її умова, опис роботи програми, спосіб її реалізації, код програми з коментарями, тести(вхідні та вихідні дані) та можливість її запустити й перевірити правильність виконання.

4. При виборі пункту «Відомості про виконавця» користувачу буде доступна інформація про виконавця даної розрахунково-графічної роботи