취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11690번 문제인 LCM(1, 2, ..., n)이다.
문제는 아래 링크를 확인하자.

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

1 이상 \(n\) 이하의 정수들의 최소공배수를 구하는 문제이다.

각 소수 \(p\)는 이 최소공배수에 몇 번 곱해져있을까? 이 값을 \(k\)라 할 때, \(k\)는 \(p^k\le n\)를 만족시키는 가장 큰 정수가 될 것이다. 이와 같은 \(p^k\)는 1 이상 \(n\) 이하의 정수이며 따라서 구하는 최소공배수는 이 수의 배수여야하기 때문이다.

\(n\) 이하의 모든 소수에 대하여 해당 소수가 최소공배수에 최대 몇 개가 포함되는지를 각각 구해 이를 곱하는 것으로 문제의 답을 구하자. \(n\) 이하의 모든 소수를 구하는 것은 에라토스테네스의 체를 이용하면 빠르게 해낼 수 있다. 이 과정에서 메모리초과가 나지 않게끔 유지하자. 각 수가 소수인지 여부만을 저장하는 것은 각수마다 1비트만 이용해도 충분함을 이용하면 이를 어렵지 않게 해낼 수 있을 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

vector<bool> sieve(99999999);
void sieveinit() {
	for (int i = 2; i * i < 99999999; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 99999999; j += i) sieve[j] = 1;
	}
}

int N;
unsigned int ans = 1;

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

	sieveinit();
	
	cin >> N;
	for (int i = 2; i < 99999999; i++) {
		if (sieve[i]) continue;
		int NN = N;
		while (NN >= i) {
			NN /= i;
			ans *= i;
		}
	}

	cout << ans;
}