특정 숫자 'k'의 거듭제곱에 해당하지 않는 처음 n개의 자연수(1부터 n까지)의 합을 구하는 프로그램입니다. 핵심 아이디어는 간단합니다. 먼저 1부터 n까지의 전체 합을 구한 뒤, 그 범위 안에 포함되는 k의 거듭제곱 값들(k, k², k³, ...)을 차례대로 빼주면 됩니다.
예제 코드
<?php
function sum_of_nums($n_val, $k_val)
{
$tot_sum = ($n_val * ($n_val + 1)) / 2;
$pow_val = $k_val;
while ($pow_val <= $n_val)
{
$tot_sum -= $pow_val;
$pow_val *= $k_val;
}
return $tot_sum;
}
$n_val = 20; $k_val = 3;
print_r("3의 거듭제곱이 아닌 처음 20개 자연수의 합은 ");
echo sum_of_nums($n_val, $k_val);
?>
출력 결과
3의 거듭제곱이 아닌 처음 20개 자연수의 합은 198
코드 동작 설명
sum_of_nums라는 이름의 함수가 정의되어 있으며, 이 함수는 특정 값의 거듭제곱에 해당하지 않는 자연수들의 합을 계산합니다. 함수에는 두 개의 매개변수가 전달됩니다. 하나는 자연수의 개수를 나타내는 n이고, 다른 하나는 거듭제곱의 밑이 되는 k입니다.
함수 내부의 처리 과정은 다음과 같습니다.
- 등차수열 합 공식인
n(n+1)/2를 이용해 1부터 n까지의 전체 합을 먼저 계산합니다. - 변수
$pow_val을 k로 초기화한 후, while 반복문을 통해 n 이하인 모든 k의 거듭제곱 값을 전체 합에서 차감합니다. - 거듭제곱 값은 매 반복마다 k를 곱해 갱신되며, n을 초과하면 반복이 종료됩니다.
함수 외부에서는 n과 k에 각각 20과 3이라는 값을 지정하고, 이 값들을 인자로 함수를 호출합니다. 최종 결과가 콘솔에 출력됩니다.
결과 검산
n=20, k=3인 경우를 직접 확인해 보겠습니다.
- 1부터 20까지의 합: 20 × 21 ÷ 2 = 210
- 20 이하의 3의 거듭제곱: 3, 9 (27은 20을 초과하므로 제외)
- 최종 결과: 210 − 3 − 9 = 198
이처럼 일일이 더하는 대신 전체 합에서 거듭제곱 값만 빼는 방식을 사용하기 때문에 시간 복잡도는 O(logk n)으로 매우 효율적이며, n이 큰 경우에도 빠르게 결과를 얻을 수 있습니다.