[c++][백준 21919][에라토스테네스의 체][유클리드 호제법] 소수 최소 공배수 - 컴도리돌이

---

21919번: 소수 최소 공배수

---

풀이과정

1. 주어진 입력 값중에서 소수가 존재하는지 판정한다. -> 에라토스테네스의 체를 이용하여 소수를 찾는다.

 

에라토스테네스의 체 : 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘으로 임의의 수 n까지의 소수르 구하고자 할 때 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다.

 

시간 복잡도 : O(Nlog(logN))

 

2. 소수가 존재할 경우 -> 유클리드 호제법을 이용하여 최대 공약수를 구한다.

 

시간 복잡도 : O(log(N))

 

3. 주의 사항 : 최소 공배수의 크기를 고려할 것.

---

#include<iostream>
#include<cmath>

using namespace std;


bool is_Prime(long long x){

    if(x < 2) return false;

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

long long gcd(long long a, long long b){

    while(b > 0){
        long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm(long long a, long long b){
    return a * b / gcd(a,b);
}

void solution(){
    int n;
    cin >> n;
    long long answer = 1;
    for(int i=0,input; i<n; i++){
        cin >> input;
        if(is_Prime(input)) 
            answer = lcm(answer,input);
    }
    if(answer == 1) cout << -1;
    else cout << answer;
}

int main(void){
    solution();
    return 0;
}