[Baekjoon] [11690 : LCM(1, 2, ..., n)]

이번 문제는 11690번 LCM(1, 2, ..., n)입니다.

 

문제는

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

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

다음과 같습니다.

 

문제를 해결하기 위해서..

입력받은 수보다 낮은 소수들의 거듭제곱의 최대들만 곱하면 LCM이 되리라 생각하고

 

중복을 막고자 마지막에서 여러 쌩쇼를 했고

int 배열의 최대 사이즈가 10^7이기에 입력인 10^8을 커버하고자 vector까지 써봤는데요.

 

이번에는 메모리 초과로 나타나서 안 되더군요

#include<stdio.h>
#include<vector>

using namespace std;

//int arr[10000001] = {1,1};
vector <int> arr(100000000);
int main(void)
{
    for(long long int i = 2; i<10000; i++)
    {
        if(arr[i] == 0)
        {
            for(long long int j = i*i; j<100000000; j+=i)
            {
                arr[j] = 1;    
            }
            for(long long int j = i*i; j<100000000; j*=i)
            {
                arr[j] = i;
            }
        }
    }

    unsigned long long int d = (unsigned long long int) 1<<32;
    unsigned long long int n, lcm=1;
    
    scanf("%llu",&n);

    // for(long long int i = 1; i<1000; i++)
    // {
    //     printf("%d ", arr[i]);
    //     if(i%10 == 0)
    //     {
    //         printf("\n");
    //     }
    // }

    for(long long int i = n; i>=2; i--)
    {
        if(arr[i] != 1) //0 : prime, 1: not prime, else : nearly prime
        {
            if(arr[arr[i]] == 0 && arr[i] != 0) //nearly prime
            {
                // printf("i : %llu lcm : %llu, arr[i] : %d arr[arr[i]] : %d\n\n",i,lcm,arr[i],arr[arr[i]]);
                lcm *= i;
                arr[arr[i]] = 1;
            }
            else if(arr[i] == 0) // prime
            {
                // printf("i : %llu lcm : %llu, arr[i] : %d arr[arr[i]] : %d\n\n",i,lcm,arr[i],arr[arr[i]]);
                lcm *= i;
                arr[i] = 1;
            }
        }
    }

    printf("%llu",lcm%d);

    return 0;
}

 

그래서 다른 방법을 생각해보기로 했습니다.

 

..

배열을 그냥 통짜로 가져오면 아무래도 메모리가 많이 소요되는 것 같아

소수만 뽑아서 가져오고

하나의 소수에 대해서 n보다 작은 동안 n제곱하여 해당하는 소수의 거듭제곱을 찾겠습니다.

 

범위를 위해서 벡터를 써야하고..

 

#include<stdio.h>
#include<vector>

using namespace std;

vector<int> prime;
bool arr[100000001];

int main(void)
{
    long long int mod = (long long int) 1<<32;
    unsigned long long int n;
    unsigned long long int lcm = 1;

    scanf("%llu",&n);

    arr[0] = 1;
    arr[1] = 1;

    for(long long int i=2; i<100000001; i++)
    {
        if(arr[i] == 0)
        {
            prime.push_back(i);
            for(long long int j=i*i; j<100000001; j+=i)
            {
                arr[j] = 1;
            }
        }
    }

    for(int i=0; i<prime.size(); i++)
    {
        unsigned long long int cnt=1;
        while(prime[i]*cnt <= n)
        {
            //printf("prime i : %d\n",prime[i]);
            cnt *= prime[i];
        }
        lcm *= cnt;
    }
    
    printf("%llu",lcm%mod);

    return 0;
}

 

그냥 에라토스테네스의 체에서 i범위를 늘려도 에러가 안나네요?

그래야 필요한 소수를 다 받을 수 있어서 이렇게 만들어줍니다~

 

끗

 

https://2heedu.tistory.com/53

배열 최대 크기

배열의 최대 크기에 관한 글입니다.

char 배열 최대 크기 : 약 백만

문제에서 최대 범위가 백만까지 주어질 경우 사용 가능

 

int 배열 최대 크기 : 약 이십오만

문제에서 최대 범위가 이십오만까지 주어질 경우 사용 가능

 

vector의 push_back 최대 크기 : 약 십억 

문제에서 최대 범위가 십억까지 주어질 경우 사용 가능