이 튜토리얼에서는 C++를 사용하여 주어진 범위 안에서 최소 약수(가장 작은 인수)가 K인 숫자의 개수를 구하는 프로그램을 살펴봅니다.
문제의 조건은 간단합니다. 범위 [a, b]가 주어졌을 때, 이 범위에 속한 숫자 중에서 가장 작은 약수가 정확히 K인 수의 개수를 세는 것이 우리의 과제입니다.
접근 방법
어떤 수 n의 최소 약수가 K가 되려면 아래 두 가지 조건을 동시에 만족해야 합니다.
- K는 반드시 소수여야 합니다. K가 합성수라면 K보다 작은 약수가 항상 존재하기 때문에, 어떤 수의 최소 약수가 K일 수 없습니다.
- n은 K로 나누어 떨어지지만, 2부터 K-1까지의 어떤 수로도 나누어 떨어지지 않아야 합니다.
따라서 먼저 K가 소수인지 검사하고, K가 소수가 아니라면 답은 곧바로 0이 됩니다. K가 소수인 경우에는 범위 내의 모든 숫자를 하나씩 확인하며 위 조건을 만족하는지 검사한 뒤 개수를 세면 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// K가 소수인지 검사하는 함수
bool if_prime(int k){
if (k <= 1)
return false;
for (int i = 2; i < k; i++)
if (k % i == 0)
return false;
return true;
}
// num이 2부터 k-1까지의 수로는 나누어 떨어지지 않고,
// k로만 나누어 떨어지는지 검사하는 함수
int check(int num, int k){
int flag = 1;
for (int i = 2; i < k; i++) {
if (num % i == 0)
flag = 0;
}
if (flag == 1) {
if (num % k == 0)
return 1;
else
return 0;
}
else
return 0;
}
// 조건을 만족하는 숫자의 개수를 세는 함수
int findCount(int a, int b, int k){
int count = 0;
if (!if_prime(k))
return 0;
else {
int ans;
for (int i = a; i <= b; i++) {
ans = check(i, k);
if (ans == 1)
count++;
else
continue;
}
}
return count;
}
int main(){
int a = 2020, b = 6300, k = 29;
cout << findCount(a, b, k);
return 0;
}
실행 결과
28
코드 설명
if_prime() 함수는 2부터 k-1까지의 모든 수로 나누어 보아 K가 소수인지 판별합니다. 나누어 떨어지는 수가 하나라도 있으면 소수가 아니므로 false를 반환합니다.
check() 함수는 flag 변수를 이용해 해당 숫자가 2부터 k-1 사이의 어떤 수로도 나누어 떨어지지 않는지 확인합니다. 이 조건을 통과한 경우에만 k로 나누어 떨어지는지를 검사하여, 최소 약수가 k인지 여부를 판단합니다.
findCount() 함수는 전체 흐름을 제어합니다. k가 소수가 아니면 즉시 0을 반환하고, 소수라면 범위 [a, b]의 모든 숫자를 순회하면서 check()를 호출해 조건을 만족하는 수의 개수를 누적합니다.
예제에서는 a = 2020, b = 6300, k = 29로 설정했으며, 실행 결과 2020부터 6300 사이에서 최소 약수가 29인 숫자는 총 28개임을 확인할 수 있습니다.
복잡도 및 최적화 팁
이 코드의 시간 복잡도는 범위의 크기와 k에 비례하여 대략 O((b-a+1) × k)입니다. 성능을 더 개선하려면 2부터 k-1까지의 모든 수 대신 k보다 작은 소수만 검사하면 됩니다. 합성수로 나누어 떨어진다면 그 합성수의 소인수로도 반드시 나누어 떨어지기 때문에, 소수에 대한 검사만으로 동일한 결과를 얻을 수 있습니다.