[백준 11690번] LCM(1, 2, ..., n)

 

문제 링크: https://www.acmicpc.net/problem/11690

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

<문제 풀이>

n 이하의 소수들에 대해서 각 소수들의 n 이하의 거듭제곱의 최댓값을 구해서 모두 곱하면 됩니다.

 

<시간 초과 주의할 점>

에라토스테네스의 체를 사용할 때 sqrt(n) 사용

 

배열의 true값를 이용해서 소수를 사용할 때 짝수번째 인덱스는 확인하지 말고 홀수번째만 확인

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
ll mod = (ll)1 << 32;
bool is_prime[100000001];
vector<int> plist;
 
void sieve(int n) {
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = i*i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    sieve(n);
    ll res = 1;
    plist.push_back(2);
    for (int i = 3; i <= n; i+=2) {
        if (is_prime[i])plist.push_back(i);
    }
    for (auto& prime : plist) {
        ll power = prime;
        while (power * prime <= n) {
            power *= prime;
        }
        res = (res * power) % mod;
    }
    cout << res;
    return 0;
}