[BOJ 11690] LCM(1, 2, ..., n)

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

11690번: LCM(1, 2, ..., n)

 

- 문제 요약

 

자연수 n이 주어졌을 때, 1부터 n까지 모든 자연수의 최소공배수를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

단순하게 에라토스테네스의 체를 코드로 구현해서 풀면 됩니다.

 

 

- 코드 작성

 

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

#define MAX 100000001
typedef long long ll;
int n;
ll result=1,mod=(ll)1<<32;
bool check[MAX];
vector<int>v;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=2;i<=n;i++){
		check[i]=true;
	}
	for(int i=2;i*i<=n;i++){
		if(!check[i]){
			continue;
		}
		for(int j=i*i;j<=n;j+=i){
			check[j]=false;
		}
	}
	v.push_back(2);
	for(int i=3;i<=n;i+=2){
		if(check[i]){
			v.push_back(i);
		}
	}
	for(auto &i:v){
		ll a=i;
        while(a*i<=n){
        	a*=i;
		}
		result=(result*a)%mod;
	}
	cout<<result;
}

코드 제출 결과