[Project Euler #5][C++] 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

문제5 : 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

문제

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

문제 해결 방법

하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.

• 문제의 조건을 만족시키는 범위를 알 수 없는 수를 찾기 위해 unsigned long long int 자료형을 사용하였다.
  • 표현 가능 범위 : 0 ~ 18,446,744,073,709,551,615
• 2중 for 문을 사용하였다.
  • 시간 복잡도 : O(n²)
  • 1부터 ULLONG_MAX까지 순회하는 for 문
  • 1부터 N(20)까지 순회하는 for 문
• 1부터 ULLONG_MAX까지 순회하는 수 중에서, 1부터 N(20)까지 모두 나누어 떨어지는 수가 있으면 순회를 중단하고 그 수를 정답으로 출력하도록 하였다.

소스 코드

#include <iostream>
#include <climits>  // ULLONG_MAX
using namespace std;
 
#define N 20
 
int main() {
    unsigned long long int i, j, ans = 0;                                                                                       
    
    for (i = 1; i <= ULLONG_MAX; i++) {
        for (j = 1; j <= N; j++) {
            if (i % j == 0) {
                if (j == N) {
                    ans = i;
                    break;
                }
            }
            else {
                break;
            }
        }
        if (ans != 0) {
            break;
        }
    }
 
    cout << ans << endl;
    
    return 0;
}

정답

232792560

심화 공부

최소공배수(Least Common Multiple)

여러 개의 정수 $n_{1}, n_{2}, \dots, n_{k} \in Z : n_{k} \neq 0$ 의 최소공배수 $lcm\{n_{1}, n_{2}, \dots, n_{k}\}$ 은 재귀적으로 $lcm\{lcm\{n_{1}, n_{2}, \dots, n_{k-1}\}, n_{k}\}$ 로 정의할 수 있다.

---

문제 출처 : https://euler.synap.co.kr/problem=5