Автор Дима задал вопрос в разделе Другие языки и технологии
Проверка на простое число и получил лучший ответ
Ответ от Дмитрий М[новичек]
курить решето эратосфена, или например вот:
есть более мозго**ные методы, но подозреваю тебе не нужны простые числа о**ительной длины )
Ответ от Ottvett[гуру]
1. Достаточно от 2 до N/2.
2. Выход из цикла, как только найден первый целочисленый делитель.
3. Проверять деление на 2, а далее - только нечетные делители (цикл с шагом 2)
При многократной проверке может быть оправдано:
4. Проверять не все делители, а только простые числа. Для этого создать предварительно массив с ними.
5. Гибрид: проверка с несколькимм простыми числами из массива, а далее c каждым нечетным, причем, достаточно до N/(простое число, следующее за последним из массива)
6. Если заранее известен диапазон проверяемого числа, заранее создать массив с простыми числами в этом диапазоне и проверять на = им
Скорее всего, самым быстрым будет:
сначала проверка деления на 2,3,5,7,11
потом на проверка деления 13,15,17,19...N/13 с шагом 2
Выбор оптимума 7-11-13-17 и т. п. требует специального исследования.
1. Достаточно от 2 до N/2.
2. Выход из цикла, как только найден первый целочисленый делитель.
3. Проверять деление на 2, а далее - только нечетные делители (цикл с шагом 2)
При многократной проверке может быть оправдано:
4. Проверять не все делители, а только простые числа. Для этого создать предварительно массив с ними.
5. Гибрид: проверка с несколькимм простыми числами из массива, а далее c каждым нечетным, причем, достаточно до N/(простое число, следующее за последним из массива)
6. Если заранее известен диапазон проверяемого числа, заранее создать массив с простыми числами в этом диапазоне и проверять на = им
Скорее всего, самым быстрым будет:
сначала проверка деления на 2,3,5,7,11
потом на проверка деления 13,15,17,19...N/13 с шагом 2
Выбор оптимума 7-11-13-17 и т. п. требует специального исследования.
Ответ от 3 ответа[гуру]
Привет! Вот подборка тем с похожими вопросами и ответами на Ваш вопрос: Проверка на простое число