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

Ответ от Jurii[гуру]
В общем виде алгоритм для каждого числа можно представить так:
Пусть дан массив «первых простых чисел» {2, 3, 5, 7, 11, …}. (Ну к примеру все простые числа меньше 100 или 1000, которые можно получить с помощью другой простейшей программы и описать в твоей программе как константы или подгрузить из внешнего файла. Всё на твоё усмотрение. )
Тогда любое натуральное число можно назвать простым если выполняются следующие условия:
— это число входит в массив «первых простых»
— это число не делится без остатка на каждое из «первых простых» и на любое нечётное число больше максимального из «первых простых» и не больше квадратного корня из проверяемого числа
Последнее это к примеру [v(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, т. к. операция деления очень затратная по времени.

Ответ от 3 ответа[гуру]

Ответ от 3 ответа[гуру]