(C언어)프로젝트 오일러(Project Euler) 3.가장 큰 소인수 구하기

문제

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

코드

#include <stdio.h>

int main(void)
{
    int divisor;    //나눗수
    long long quotient = 600851475143;

    for (divisor = 2; divisor <= quotient; divisor++)
    {
        if (quotient % divisor == 0)
        {
            quotient = quotient / divisor;   //몫을 다시 나눠지는 수로 설정
            printf("%d\n", divisor);
        }
    }
    
    return 0;
}

A를 B로 나누어 C란 몫으로 나누어떨어진다면,
C를 다시 D로 나누는 연산을 반복하며 소인수분해를 시행한다.

A는 C로 대체되므로 C를 quotient라 이름 지었다.
나누는 수인 B와 D는 divisor라 이름 지었다.

 

정답:

6857