Как проверить, что число простое
Короткий ответ
Простое число делится только на 1 и на себя. Достаточно проверить делители до квадратного корня:
boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; (long) i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
void main() {
IO.println(isPrime(17));
IO.println(isPrime(21));
IO.println(isPrime(1));
}Результат:
true
false
falseВсе простые до N
Отфильтруйте диапазон чисел той же проверкой:
boolean isPrime(int n) {
return n > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(n)).noneMatch(i -> n % i == 0);
}
void main() {
IO.println(IntStream.rangeClosed(1, 30).filter(this::isPrime).boxed().toList());
}Результат:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]Очень большие числа
Для огромных чисел у BigInteger есть вероятностная проверка — при параметре 20 ошибка практически невозможна:
void main() {
var big = new BigInteger("170141183460469231731687303715884105727");
IO.println(big.isProbablePrime(20));
}Результат:
trueЧастая ошибка
Считать 1 простым числом или проверять делители до n. Первое даёт неверный ответ, второе — медленный код. Условие i * i <= n в int может переполниться для чисел около Integer.MAX_VALUE, поэтому в первом примере умножение идёт в long.
Функции из этого ответа
- Math.sqrt() — Возвращает квадратный корень числа.
- IntStream.range() — Создаёт поток целых чисел из диапазона.
- BigInteger — Целое число любого размера — когда не хватает даже long.