고유한 소인수란?
고유한 소인수(unique prime factor)는 어떤 수의 약수이면서 동시에 소수인 수를 말합니다. 소수란 1과 자기 자신, 단 두 개의 약수만을 가지는 수입니다. 이 문제의 목표는 주어진 숫자의 모든 고유한 소인수를 찾아 그 곱을 계산하는 것입니다.
예를 들어 n = 1092라고 가정해 보겠습니다. 1092의 소인수는 2, 3, 7, 13이며, 이들의 곱은 546입니다.
기본 접근 방법
가장 직관적인 방법은 2부터 n까지의 모든 수를 하나씩 확인하면서, n의 약수이면서 동시에 소수인 값을 찾아 곱하는 것입니다.
입력: n = 10 출력: 10
동작 원리
입력값 10의 소인수는 2와 5 두 개뿐이므로, 두 수의 곱인 10이 결과로 출력됩니다.
구현 순서는 다음과 같습니다.
- i를 2부터 n까지 증가시키며 반복합니다.
- i가 n의 약수인지 확인합니다(n % i == 0).
- i가 소수인지 별도의 내부 반복문으로 검사합니다.
- i가 소수라면 product 변수에 곱해 저장합니다.
- i가 n에 도달할 때까지 반복한 뒤 product를 출력합니다.
예제 코드
#include <iostream>
using namespace std;
int main() {
int n = 10;
long long int product = 1;
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
int isPrime = 1;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = 0;
break;
}
}
if (isPrime) {
product = product * i;
}
}
}
cout << product;
return 0;
}
더 효율적인 방법: O(√n)
위 코드는 이중 반복문 구조 때문에 시간 복잡도가 O(n²)로, n이 커지면 실행 속도가 급격히 느려집니다. 다음과 같이 개선하면 훨씬 빠르게 처리할 수 있습니다.
- i를 2부터 √n까지 증가시키며, n이 i로 나누어 떨어지면 product에 i를 한 번만 곱합니다.
- n이 i로 나누어 떨어지는 동안 계속 n을 i로 나누어 같은 소인수가 중복으로 곱해지지 않도록 합니다.
- 반복이 끝난 후 남은 n이 1보다 크다면 그 값 자체가 소수이므로 product에 곱합니다.
#include <iostream>
using namespace std;
int main() {
int n = 1092;
long long int product = 1;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
product *= i;
while (n % i == 0)
n /= i;
}
}
if (n > 1)
product *= n;
cout << product;
return 0;
}
이 최적화된 방법은 시간 복잡도가 O(√n)으로, 큰 수에 대해서도 빠르게 동작합니다. 실제 프로젝트나 코딩 테스트에서는 상황에 맞게 두 방식 중 효율적인 쪽을 선택하는 것이 좋습니다.