[c++] 백준 21919 : 소수 최소 공배수

 

[c++] 백준 21919 : 소수 최소 공배수

🥈실버 3

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

21919번: 소수 최소 공배수

---

접근

1. 에라토스테네스의 체를 활용하여 문제에서 제시한 최대치의 값까지 소수를 판별한다.
2. 제한 수가 1,000,000이므로 long long으로 자료형을 선언하지 않으면 오답처리가 된다.
3. 입력 값들 중에 소수로 판별되는 것들을 벡터에 집어 넣는다.
4. 벡터가 비어있는 경우 소수가 없던 것이므로 -1을 출력한다.

 

3개 이상의 수에서 최소공배수를 계산하는 법

A, B, C, D.. 이렇게 복수의 수가 있는 경우,

A, B의 최소공배수를 먼저 구한다.

그렇게 나온 값과 C의 최소공배수를 구한다.

그렇게 나온 값과 D의 최소공배수를 구한다....(반복)

 

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
  if ( b == 0 ) return a;
  return gcd(b, a%b);
}

ll lcd(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll ans = 0;

  int N;
  cin >> N;

  bool arr[1000001];
  memset(arr, true, sizeof(arr)); // 전부 true로 초기화

  for (int i =2; i <= sqrt(1000000); i++) { // 에라토스테네스의 채 활용
    if (arr[i]) { // 만약 소수를 만났다?
      //소수에 어떤 값을 곱해도 합성수이므로 그 배수들을 전부 false처리.
      for(int j=i*i; j <= 1000000; j+=i){
        arr[j] = false;
      }
    }
  }
  vector<int> vec;
  
  while(N--) {
    ll num;
    cin >> num;
    if (arr[num]) { // 소수가 맞으면 vec에 넣기
      vec.push_back(num);
    }
  }
  if (vec.empty()) { // 소수가 없으면 -1 출력
    cout << -1; 
  }
  else {
    ans = vec[0];	// 첫번째 소수를 미리 뺴놓고
    for (int i = 0; i < vec.size()-1; i++) {	// 나머지 값들을 순회하면서 최소공배수를 구한다.
      ans = lcd(ans, vec[i+1]);
    }
    cout << ans;
  }
  
  return 0;
}