C++로 배열의 모든 요소로 나누어 떨어지는 범위 내 숫자 개수 구하기

두 개의 정수 START와 END가 주어져 하나의 숫자 범위를 정의하고, 양수로만 이루어진 배열 Arr[]도 함께 제공됩니다. 목표는 [START, END] 범위 안에 있으면서 배열의 모든 요소로 나누어 떨어지는 숫자를 모두 찾아 그 개수를 구하는 것입니다.

이 문제를 해결하는 대표적인 두 가지 방법을 살펴보겠습니다.

예시로 이해하기

입력

START=1 END=20 Arr[]= { 2, 4, 8 }

출력

배열의 모든 요소로 나누어 떨어지는 숫자의 개수: 2

설명

범위 내에서 배열의 모든 요소(2, 4, 8)로 나누어 떨어지는 숫자는 8과 16입니다.

입력

START=100 END=200 Arr[]= { 230, 321, 490, 521 }

출력

배열의 모든 요소로 나누어 떨어지는 숫자의 개수: 0

설명

100부터 200 사이에는 배열의 어떤 요소로도 나누어 떨어지는 숫자가 존재하지 않습니다.

방법 1: 완전 탐색(Naive Approach)

가장 직관적인 방법은 START부터 END까지의 모든 숫자를 하나씩 순회하면서, 각 숫자가 배열의 모든 요소로 나누어 떨어지는지 검사하는 것입니다. 조건을 만족하면 카운트를 증가시킵니다.

알고리즘 동작 과정

정수 START와 END를 범위 변수로 받습니다.
함수 divisiblebyArr(int start, int end, int arr[], int len)는 범위 변수와 배열을 인자로 받아, 배열의 모든 요소로 나누어 떨어지는 숫자의 개수를 반환합니다.
해당하는 숫자의 개수를 저장할 변수 count를 0으로 초기화합니다.
조건 만족 여부를 표시할 변수 flag를 선언합니다.
for 반복문으로 i=start부터 i=end까지 범위의 숫자를 순회합니다.
각 숫자 num=i에 대해 while 반복문으로 배열의 모든 요소에 대한 나눗셈 가능 여부를 검사합니다.
모든 요소가 num을 나눌 수 있으면 flag=1로 설정합니다.
while 반복문이 끝난 후 flag가 1이면 count를 증가시킵니다.
모든 반복이 끝나면 count에는 배열의 모든 요소로 나누어 떨어지는 숫자의 총 개수가 저장됩니다.
count를 결과로 반환합니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;
int divisiblebyArr(int start, int end, int arr[], int len){
    int count = 0;
    int flag=0;
    int index=0;
    for (int i = start; i <= end; i++){
        int num = i;
        index=0;
        while(index<len){
            if(num % arr[index++] == 0)
                { flag=1; }
            else{
                flag=0;
                break;
            }
        }
        if (flag == 1)
            { count++; }
        }
    return count;
}
int main(){
    int START = 5, END = 20;
    int Arr[] = {2,4,8 };
    int len=sizeof(Arr)/sizeof(Arr[0]);
    cout <<"배열의 모든 요소로 나누어 떨어지는 숫자의 개수: "<< divisiblebyArr(START,END,Arr,len);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

배열의 모든 요소로 나누어 떨어지는 숫자의 개수: 2

방법 2: 최소공배수(LCM) 활용

더 효율적인 방법은 배열의 모든 요소의 최소공배수(LCM)를 먼저 구한 뒤, [START, END] 범위 내에서 해당 LCM으로 나누어 떨어지는 숫자를 찾아 개수를 세는 것입니다. 어떤 수가 배열의 모든 요소로 나누어 떨어진다는 것은 곧 그 수가 전체 요소의 LCM으로 나누어 떨어진다는 의미이기 때문입니다.

알고리즘 동작 과정

정수 START와 END를 범위 변수로 받습니다.
함수 getLCM(int a, int b)는 두 수를 인자로 받아, while 반복문으로 두 수 모두 나누어 떨어지는 첫 번째 수를 찾아 LCM으로 반환합니다.
함수 getLCMArray(int arr[], int n)는 배열과 그 길이를 입력받아 배열의 모든 요소의 LCM을 반환합니다.
먼저 getLCM(arr[0], arr[1])로 초기 LCM을 계산한 후, i=2부터 i<n까지 이전 LCM과 arr[i]의 LCM을 getLCM(lcm, arr[i]) 호출로 연속적으로 구합니다.
함수 divisiblebyArr(int start, int end, int arr[], int len)는 범위 변수와 배열을 인자로 받아, 배열의 모든 요소로 나누어 떨어지는 숫자의 개수를 반환합니다.
해당하는 숫자의 개수를 저장할 변수 count를 0으로 초기화합니다.
변수 lcm을 getLCMArray(arr, len)의 결과값으로 설정합니다.
for 반복문으로 i=start부터 i=end까지 범위의 숫자를 순회합니다.
각 숫자 i가 lcm으로 나누어 떨어지는지 검사하고, 참이면 count를 증가시킵니다.
모든 반복이 끝나면 count에는 배열의 모든 요소로 나누어 떨어지는 숫자의 총 개수가 저장됩니다.
count를 결과로 반환합니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;
int getLCM(int a, int b){
    int m;
    m = (a > b) ? a : b;
    while(true){
        if(m % a == 0 && m % b == 0)
            return m;
        m++;
    }
}
int getLCMArray(int arr[], int n){
    int lcm = getLCM(arr[0], arr[1]);
    for(int i = 2; i < n; i++){
        lcm = getLCM(lcm, arr[i]);
    }
    return lcm;
}
int divisiblebyArr(int start, int end, int arr[], int len){
    int count = 0;
    int flag=0;
    int lcm=getLCMArray(arr,len);
    for (int i = start; i <= end; i++){
        if(i%lcm==0)
            { count++; }
        }
    return count;
}
int main(){
    int START = 5, END = 20;
    int Arr[] = {2,4,8 };
    int len=sizeof(Arr)/sizeof(Arr[0]);
    cout <<"배열의 모든 요소로 나누어 떨어지는 숫자의 개수: "<< divisiblebyArr(START,END,Arr,len);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

배열의 모든 요소로 나누어 떨어지는 숫자의 개수: 2

마무리

완전 탐색 방식은 각 숫자마다 배열의 모든 요소를 일일이 검사해야 하므로 시간 복잡도가 O((END−START)×len)입니다. 반면 LCM을 활용하면 LCM 계산 후 단순 나눗셈 검사만 하면 되므로, 특히 범위가 넓거나 배열이 길 때 훨씬 효율적입니다. 다만 배열 요소가 큰 경우 LCM 값이 매우 커질 수 있으므로 오버플로우에 유의해야 합니다.