Блок-схемы

Составить блок-схему

Задание 1.

Алгоритм нахождения простого числа.

Требуется составить алгоритм (в виде блок-схемы), который бы определял, является ли заданное число простым или нет.

Допустим, входными данными будет число N. Как определить, является ли оно простым или нет?

1 вариант. Можно последовательно делить N на числа в интервале от 2 до N-1, Если при делении N на какое-либо из этих чисел остатка не остается, то число не является простым, если же все числа перебраны, а остаток от деления остается, значит, число является простым. Является ли алгоритм эффективным? Почему? 

2 вариант. Можно последовательно делить N на числа в интервале от 2 до N/2. При делении числа N на числа от N/2+1 до N-1 результат будет варьироваться в диапазоне от 1.999 до 1.001, что явно дает остаток, а, значит, не удовлетворяет нашим условиям. Можно ли улучшить данный алгоритм?

3 вариант. Если мы последовательно перебираем делители числа N, то сам делитель будет увеличиваться, а результат деления при увеличении делителя - уменьшаться. Это будет наблюдаться до некоторого числа h, при котором и делитель и результат деления будут равны. При увеличении делителя больше числа h делитель будет увеличиваться в тому же диапазоне, в котором ранее уменьшался результат деления. Чему равно число h? Какой тогда будет оптимизированный интервал увеличения делителя?

Задание 2

Составить алгоритм (в виде блок-схемы) который бы считал количество чисел в разных диапазонах.

Допустим, у нас есть 4 диапазона чисел 1-25, 26-50, 51-75, 76-100. Как подсчитать количество простых чисел содержащихся в каждом из этих диапазонов?

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

1 вариант. На примере второго диапазона.  Создаем счетчик. Проверяем последовательно каждое число от 1 до верхней границы второго диапазона, если оно простое прибавляем к счетчику единицу. Затем из значения счетчика вычитаем количество предыдущего (первого) диапазона. В чем будут заключаться отрицательные стороны работы алгоритма?

2 вариант. Можно последовательно перебирать только числа данного диапазона. Это ускорит работу алгоритма, но вместе с тем усложнит его.

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

P.S. Отчет должен включать постановку каждой из задач, аналитическую часть и решение. В отчете расписать все вопросы приведенные в теле задачи.