21919 소수 최소공배수

여러 수들이 주어졌을 때,

소수를 찾고, 그 소수들의 최소 공배수를 구하는 문제

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

1. 문제

---

간단 설명

위에 설명한 그대로임

길이가 N인 수열 A에서 소수들을 골라 최소공배수를 구할 것

2. 문제 분석

---

필요변수

수열의 길이 N (1<= N <= 10,000)

수열의 원소 A_i가 공백으로 주어짐

A_i 는 2 <= A_i <= 1,000,000 의 범위를 가진다

수열을 저장할 벡터 v

답은 2^63 미만인 입력만 주어진다

주의점

1. 답은 2^63 미만이다. 즉, int형으로는 처리 불가
2. 중복인 원소가 주어질 수도 있다

알고리즘

1. N 입력받기
2. N번 입력받으면서, 그 수가 소수인지 먼저 판별 후, 소수라면 v에 넣는다
    - 소수 판별은 에라체를 이용해도 가능하지만, N과 A가 크지 않아 직접 계산함
3. 원소의 중복을 제거
    - cpp의 unique 함수 사용 전에는 꼭 정렬해주어야함
4. 소수인 원소들의 최소공배수를 출력한다
    - 보통 a * b / gcd(a, b)로 최소 공배수를 구하지만, 소수는 자기 자신 외에는 나눠지는 수가 없으므로
    그냥 두 수를 곱하는게 최소 공배수가 된다.

소수 판별에 관련 내용은 이 글 참조 1990 소수인 펠린드롬

3. 소스코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>

using namespace std;

// n이 소수인지 판별하는 함수
bool IsPrime(int n) {
	// 수학적 증명에 의해 2~sqrt(N)까지만 나눠도 소수인지 판별 가능함
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N;
	vector<int> v;
	cin >> N;

	// 1. 소수인 수만 벡터에 삽입
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		if (IsPrime(tmp))
			v.push_back(tmp);
	}

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

	// cpp에선 중복 원소 제거하기전, 정렬 필요
	sort(v.begin(), v.end());
	unique(v.begin(), v.end());

	// 2. 최소 공배수 구하기
	unsigned long long res = 1;
	for (int e : v) {
		res = lcm(res, e);
	}

	cout << res;
	
	return 0;
}