어떤 숫자 'x'가 주어졌을 때, 그 숫자로 나누어 떨어지는 팩토리얼(계승)을 가진 첫 번째 자연수를 찾아야 하는 경우가 있습니다. 예를 들어 x가 16이라면 1!부터 5!까지는 16으로 나누어 떨어지지 않지만, 6! = 720 = 16 × 45이므로 정답은 6이 됩니다.
이를 구현하는 PHP 코드는 다음과 같습니다.
예제 코드
<?php
function factorial_num($x_val)
{
$fact_num = 1;
for ($i = 1; ; $i++)
{
$fact_num = $fact_num * $i;
if ($fact_num % $x_val == 0)
break;
}
return $i;
}
$x_val = 16;
print_r("16으로 나누어 떨어지는 팩토리얼을 가진 첫 번째 자연수는 ");
echo(factorial_num($x_val));
?>실행 결과
16으로 나누어 떨어지는 팩토리얼을 가진 첫 번째 자연수는 6
코드 설명
위 코드의 동작 원리를 단계별로 살펴보겠습니다.
- factorial_num 함수: 매개변수로 전달받은 값 $x_val에 대해 팩토리얼을 순차적으로 계산합니다.
- 나눗셈 검사: 반복문 안에서 팩토리얼 값을 하나씩 키워 가며 나머지 연산자(%)를 사용해 $x_val로 나누어 떨어지는지 확인합니다.
- 조기 종료: 나누어 떨어지는 순간 break 문으로 반복을 멈추고 현재의 $i 값을 반환합니다.
- 함수 호출 및 출력: 함수 외부에서 16을 변수에 담아 인자로 전달한 뒤, 결과를 콘솔에 출력합니다.
단계별 계산 과정
x = 16일 때 각 단계의 팩토리얼 값은 다음과 같습니다.
- 1! = 1 → 나누어 떨어지지 않음
- 2! = 2 → 나누어 떨어지지 않음
- 3! = 6 → 나누어 떨어지지 않음
- 4! = 24 → 나누어 떨어지지 않음
- 5! = 120 → 나누어 떨어지지 않음
- 6! = 720 = 16 × 45 → 나누어 떨어짐
따라서 조건을 만족하는 첫 번째 자연수는 6입니다.
이 방식은 별도의 소인수분해 과정 없이 모듈로 연산만으로 조건을 만족하는 최솟값을 빠르게 구할 수 있다는 장점이 있습니다. 다만 x가 매우 큰 값이면 팩토리얼이 급격히 커져 정수 범위를 초과할 수 있으므로, 이런 경우에는 BCMath 또는 GMP 확장을 활용한 임의 정밀도 연산을 고려하는 것이 좋습니다.