Как вычислить факториал
Короткий ответ
Факториал n! — произведение чисел от 1 до n. Используйте long, потому что значения растут очень быстро:
long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
void main() {
IO.println(factorial(5));
IO.println(factorial(20));
}Результат:
120
2432902008176640000Рекурсией
Классическое определение: n! = n × (n − 1)!, а 0! = 1:
long factorial(int n) {
return n <= 1 ? 1 : n * factorial(n - 1);
}
void main() {
IO.println(factorial(10));
}Результат:
3628800Большие значения
21! уже не помещается в long. Для больших значений нужен BigInteger:
BigInteger factorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
void main() {
IO.println(factorial(30));
}Результат:
265252859812191058636308480000000Частая ошибка
Не заметить переполнение. long молча «заворачивается», и 21! получается отрицательным:
void main() {
long result = 1;
for (int i = 2; i <= 21; i++) {
result *= i;
}
IO.println(result);
}Результат:
-4249290049419214848Если нужно поймать переполнение, используйте Math.multiplyExact() — он выбрасывает ArithmeticException.
Функции из этого ответа
- BigInteger — Целое число любого размера — когда не хватает даже long.
- IntStream.range() — Создаёт поток целых чисел из диапазона.
- ArithmeticException — Возникает при недопустимой арифметической операции, например целочисленном делении на ноль.