[21919] 소수 최소 공배수(C++)

문제

행복이는 길이가 $N$인 수열 $A$에서 소수들을 골라 최소공배수를 구해보려고 한다.

행복이를 도와 이를 계산해주자.

 

 

입력

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. $(1 \le N \le 10,000)$ 

그 다음줄에는 수열 $A$의 원소 $A_{i}$가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 

답이 $2^{63}$ 미만인 입력만 주어진다.

 

 

출력

첫째 줄에 소수들의 최소공배수를 출력한다.

만약 소수가 없는 경우는 -1을 출력한다.

 

 

해결 방법

이 문제의 핵심은

1️⃣ 수열의 원소는 중복될 수 있음
2️⃣ 소수들의 최소공배수를 구하는 것

위와 같다.

{2, 3, 3, 4, 5, 5, 8}과 같이 수열에 중복된 원소가 들어갈 수 있는데

우리가 찾고자 하는 것은 소수의 최소공배수이기 때문에 중복된 원소를 제거할 필요가 있다.

또한, 소수의 최소공배수를 구하는 것은 일반적인 두 수의 최소공배수를 구하는 것보다 훨씬 간단하다.

소수이기 때문에 이들끼리는 공통된 배수가 없기 떄문

즉, 소수들의 최소공배수란 그냥 이들을 전부 곱한 값이 된다.

 

 

내 코드

// [21919] 소수 최소 공배수
// 정수론
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> primes;

bool isPrime(int num)
{
    for(int i = 2; i <= sqrt(num); i++) {
        if(num % i == 0) return false;
    }
    return true;
}

void input()
{
    int n, num;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> num;
        if(isPrime(num)) {
            primes.push_back(num);
        }
    }
}

long long getLCM()
{
    long long lcm = 1;
    sort(primes.begin(), primes.end());
    primes.erase(unique(primes.begin(), primes.end()), primes.end());

    for(int i = 0; i < primes.size(); i++) {
        lcm *= primes[i];
    }
    return lcm;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    if(primes.empty()) cout << "-1\n";
    else cout << getLCM() << '\n';

    return 0;
}