K!LT, задача не в нахождении всех простых чисел из этого промежутка, а выявить является ли число простым. И я вроде почти тоже самое в первом посте написал.

Eterhard, спасибо, пока не надо, вроде понял. Попробую сегодня реализовать, но я не думаю, что получится быстрее ведь придётся проверять на простоту ещё и делители(например для числа 50000 их 111) и делители делителей и т.д.

Должно быть быстрее, т.к. Перебор идет не до самого числа а до его корня, например при вычислении простое ли число 99999 идет перебор от 2х до 316,2 - 158 нечетных чисел, из них 65 простые.

почему до корня? по мойму легче и быстрее проверять число циклом числами от 3 до половины числа,прибавляя 2 после каждого цикла. и максимум будет (число / 4) повторений

LtiomaP, нет ,до корня быстрее. Например число 1000000 - по твоему методу будет 250000 повторений, а до корня 500.

да , но число может делиться на простое число после корня

LtiomaP, и что? Всё равно все делители найдутся. Например есть число 100 - берём числа до десяти - оно делится на 5 - составное. 101 - не делится на числа до 10 - простое.

надо делить на все простые числа, x < n:2-1, где x - простое число, n - исходное число.
если при делении на все числа присутствует остаток - простое. иначе - составное. можно хороший вариант с БД замутить. Можно и без..

Алгоритм Эратосфена. Выписываем все натуральные числа от 2 до N (где N-диапазон, например, 1000), выбирается первое (это 2, простое) и вычеркиваются все кратные ему числа, кроме него самого. Затем берется следующее из невычеркнутых: 3. И т.д. (тему не читал, сори если репост)

duke, проверка на простоту неэффективна. Для RSA, например, нужны 256-512 битные простые числа, их находить довольно долго, если рандомом проверять впрочем, это уже занудство и не по теме. Умолкаю.

duke, нет, до корня вполне достаточно.

.