백준 21919 소수 최소 공배수

https://www.acmicpc.net/problem/21919

21919번: 소수 최소 공배수

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;



bool isVisit[1000001];

bool isPrime(int k) {


    for (int i = 2; i <= sqrt(k); i++) {
        if (k % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;

    vector<int> prime;

    cin >> n;


    for (int i = 0; i < n; i++) {
        int temp;

        cin >> temp;

        if (isPrime(temp)) {
            prime.push_back(temp);
        }
    }

    //소수가 없는 경우 -1 출력
    if (prime.empty()) {
        cout << -1;
        return 0;
    }

    long long ans = 1;

    for (int i = 0; i < prime.size(); i++) {
        if (!isVisit[prime[i]]) {
            isVisit[prime[i]] = true;

            ans *= prime[i];
        }
    }


    cout << ans;



    return 0;
}

 

문제 그대로 구현하면 된다.

주어진 숫자에서 소수를 구한 뒤 이들의 최소공배수를 구한다.

 

소수들의 최소공배수는 이들을 곱한 것과 같다.

다만 입력으로 중복된 숫자가 들어올 수 있으므로

isVisit 배열을 추가하여 중복을 처리하였다.