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

백준 - 11690

---

풀이

N이하 소수들의 가장 큰 거듭제곱들을 곱하고, 2^32로 나눈 나머지를 출력해주면 된다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#define MAX 100000001
bool cNum[MAX];
int main(){
    for (int i = 2; i*i < MAX; i++)
        if (!cNum[i])
            for (int j = 2*i; j < MAX; j += i)
                cNum[j] = true;
				
    int n;
    scanf("%d", &n);
    long long result = 1;
    for (int i = 2; i < MAX; i++)
        if (!cNum[i]){
            long long temp = 1;
            while (temp*i <= n) temp *= i;
            result = result*temp %4294967296;
        }
    printf("%lld", result);
}

---

출처

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