C 프로그램으로 숫자의 가장 큰 소인수 구하기

소인수(Prime Factor)란?

정수론에서 소인수란 어떤 양의 정수를 나머지 없이 정확히 나누어 떨어지게 하는 소수를 의미합니다. 이러한 소수들을 찾는 과정을 정수 인수분해(integer factorization) 또는 소인수분해(prime factorization)라고 부릅니다.

예시: 288의 소인수는 다음과 같습니다.

288 = 2 × 2 × 2 × 2 × 2 × 3 × 3

문제 정의

주어진 수를 소인수분해했을 때, 그중 가장 큰 소인수를 찾는 것이 목표입니다.

입력: n = 124
출력: 31이 가장 큰 소인수입니다!

동작 원리

예를 들어 124를 소인수분해하면 124 = 2 × 2 × 31이 됩니다. 여기서 소인수는 2와 31이며, 이 중 가장 큰 값은 31입니다.

알고리즘은 다음과 같은 방식으로 동작합니다.

1. 가장 작은 소수인 2부터 시작하여 차례대로 나누어 떨어지는지 검사합니다.
2. 나누어 떨어지면 해당 값을 몫으로 대체하고, 현재 값을 최대 소인수 후보로 저장합니다.
3. 몫이 1이 되면 더 이상 나눌 수 없으므로, 마지막으로 저장된 값이 곧 가장 큰 소인수입니다.

C 언어 구현 예제

#include <stdio.h>
int main() {
    long int n;
    n = 3453;
    long int div = 2, ans = 0, maxFact;
    while(n != 0) {
        if(n % div != 0)
            div = div + 1;
        else {
            maxFact = n;
            n = n / div;
            if(n == 1) {
                printf("%d is the largest prime factor !", maxFact);
                ans = 1;
                break;
            }
        }
    }
    return 0;
}

실행 결과

n = 3453을 입력으로 넣으면 프로그램은 다음과 같은 결과를 출력합니다.

1151 is the largest prime factor !

실제로 3453 = 3 × 1151이므로, 가장 큰 소인수는 1151입니다.