Приведите алгоритмы нахождения простых чисел в заданном промежутке

решето эратосфена, на википедии есть алгоритм.

вот на си

http://pastebin.com/uAyyFcUk

В общем виде алгоритм для каждого числа можно представить так:

Пусть дан массив «первых простых чисел» {2, 3, 5, 7, 11, …}. (Ну к примеру все простые числа меньше 100 или 1000, которые можно получить с помощью другой простейшей программы и описать в твоей программе как константы или подгрузить из внешнего файла. Всё на твоё усмотрение. )

Тогда любое натуральное число можно назвать простым если выполняются следующие условия:
— это число входит в массив «первых простых»
— это число не делится без остатка на каждое из «первых простых» и на любое нечётное число больше максимального из «первых простых» и не больше квадратного корня из проверяемого числа

Последнее это к примеру [√(12343)] = 111. Это значит если число 12343 не делится ни на одно нечётное число меньше или равно 111 (потому что я отбросил дробную часть) , тогда оно является простым.

Для проверки можно просто посмотреть результат деления на 110, 111 и 112:

12343/110 = 112,2090909091
12343/111 = 111,1981981982
12343/112 = 110,2053571429

К стати: 12343 — простое число.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Алгоритм нахождения простых чисел в заданном промежутке — это применение вышеизложенного алгоритма к каждому числу заданного промежутка.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

P.S. Вышеприведённый алгоритм можно упростить в плане утверждения: «на любое нечётное число» .

Дело в том, что начиная с 5 следующие простые числа находятся только на местах числовой оси, отстоящих попеременно на 2 и 4 значения.

Т. е. : 5 + 2 = 7 — простое
7 + 4 = 11 — простое
11 + 2 = 13 — простое
13 + 4 = 17 — простое
17 + 2 = 19 — простое
19 + 4 = 23 — простое
23 + 2 = 25 — первое непростое число, которое получено по данному утверждению

Доказательство данного утверждения можно построить графически с помощью решета Эратосфена после вычёркивания чётных чисел больше 2 и кратных 3.

Это утверждение может сократить время выполнения алгоритма примерно на 1/3, т. к. операция деления очень затратная по времени.