1부터 n까지의 최소공배수를 빠르게 구하는 방법

1. 문제

 

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

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

 

2. 풀이

 

두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면..

 

a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다.

 

예를 들어 18과 24의 최소공배수를 구한다면..

 

$$18 = 2 * 3^{2}$$

 

$$24 = 2^{3} * 3$$

 

여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $3^{2}$으로 두 수를 곱하는 것이 최소공배수이다.

 

그러니까 최소공배수는 72

 

그래서 1부터 n까지 소인수분해를 해서, 나타나는 모든 소인수들에 대해 소인수 지수가 가장 큰 경우만 찾아서 곱해가지고 구할려고 했는데

 

시간초과 나오더라

 

from sys import stdin

def get_prime(n):
    
    result = [1]*(n+1)
    result[1] = 0

    for i in range(2,int((n+1)**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i+i,n+1,i):
                
                result[j] = 0
    
    return result

def factorization(n,prime_count):
    
    p = 2

    while p*p <= n:
        
        p_count = 0

        while n % p == 0:
            
            n = n//p
            p_count += 1
        
        x = prime_count.get(p,0)

        if x < p_count:
            
            prime_count[p] = p_count
        
        p += 1
    
    if n > 1:
        
        if prime_count.get(n,0) == 0:
            
            prime_count[n] = 1
    
    return prime_count

n = int(stdin.readline())

prime_list = get_prime(n)

prime_count = {}

for i in range(1,n+1):
    
    if prime_list[i] == 1:
        
        prime_count[i] = 1
    
    else:
        
        prime_count = factorization(i,prime_count)

answer = 1
mod = 2**32

for k,v in prime_count.items():

    for _ in range(v):

        answer *= k
        answer %= mod

print(answer)

 

소인수분해가 느려서 그런지 smallest prime factor를 이용해 빠르게 소인수분해해서 구해볼려고 했는데

 

그래도 안돼

 

from sys import stdin

def get_spf(n):
    
    spf = [i for i in range(n+1)]

    for i in range(2,n+1,2):
        
        spf[i] = 2

    for i in range(2,int((n+1)**(1/2))+1):
        
        if spf[i] == i:
            
            for j in range(i+i,n+1,i):
                
                if j % i == 0:

                    spf[j] = i

    return spf

def factorization(n,spf,prime_count):
    
    p_count = {}

    while n > 1:
        
        p_count[spf[n]] = p_count.get(spf[n],0) + 1

        n = n//spf[n]
    
    for k,v in p_count.items():
        
        prime_count[k] = max(prime_count.get(k,0),v)
    
    return prime_count

n = int(stdin.readline())

spf = get_spf(n)

prime_count = {}

for i in range(1,n+1):
    
    if spf[i] == i:
        
        prime_count[i] = 1
    
    else:
        
        prime_count = factorization(i,spf,prime_count)

answer = 1
mod = 2**32

for k,v in prime_count.items():

    for _ in range(v):

        answer *= k
        answer %= mod

print(answer)

 

 

여러가지 잔재주 부려서 어떻게든 풀어볼라했는데 안되더라고

 

그래서 다르게 접근해야한다는걸 알았지

 

"1부터 n까지 소인수분해를 한다면.. 나타나는 소인수는 n 이하의 소수이므로, n이하의 소수를 먼저 모두 찾는다

 

다음, 각각 소수에 대해 n 이하에서 지수의 최댓값이 얼마인지 계산하고..

 

이들을 전부 곱하면 그것이 최소공배수"

 

에라토스테네스의 체를 이용해서 n이하의 소수를 먼저 모두 찾고,

 

n이하에서 각 소수가 지수를 최대 얼마까지 가지는지 계산한다...

 

이건 어떻게 계산할 수 있지? 반복문으로 계속 곱해보는것도 있기는 하지만..

 

log를 이용해서도 구할 수 있다.

 

예를 들어 n = 32에서 2의 지수는 최대 얼마까지? $int(log_{2} (32))$

 

3의 지수는? $int(log_{3} (32))$ ...

 

...

 

여기서 문제는 $2^{32}$로 나눈 나머지를 구해야하니까.. 모듈로 연산 성질을 이용해 곱하면서 나머지를 계속 구해가지고..

 

수를 압축시켜 빠르게 계산해야겠지

 

import math
from sys import stdin

def get_prime(n):
    
    result = [1]*(n+1)

    for i in range(2,int((n+1)**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i+i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

n = int(stdin.readline())

prime_list = get_prime(n)

answer = 1

mod = 2**32

for p in prime_list:

    answer *= pow(p,int(math.log(n,p)),mod)
    answer %= mod

print(answer)

 

근데 이렇게 하면 시간초과가 아니라 메모리 초과가 나더라고

 

n의 최대가 $10^{8}$인데 result를 만들때 메모리 초과가 나나 했음

 

그래서 어떻게든 메모리 줄여볼려고 여러 잔재주를 부렸는데

 

get_prime에서 소수 리스트를 return하지 말고 result를 return해서 써먹도록 하면...

 

조금 더 채점하긴 하는데 어쨌든 메모리 초과나고

 

import math
from sys import stdin

def get_prime(n):
    
    result = [1]*(n+1)

    for i in range(2,int((n+1)**(1/2))+1):
        
        if result[i]:
            
            for j in range(i+i,n+1,i):
                
                result[j] = 0
    
    return result

n = int(stdin.readline())

prime_list = get_prime(n)

answer = 1

mod = 2**32

for i in range(2,n+1):
    
    if prime_list[i]:
        
        answer *= pow(i,int(math.log(n,i)),mod)
        answer %= (mod)

print(answer)

 

 

뭐 mod = 2**32로 저장하는 것 조차도 큰 수니까 메모리 잡아먹는다고 생각했고

 

여러 풀이 보니까 0,1  정수를 저장하지 말고 True, False bool을 저장하면 메모리 아낄수 있다고 하더라고

 

그렇게도 해봤는데 어쨌든 메모리 초과남

 

pypy3가 메모리 잡아먹는 괴물이라 더 이상 줄이기는 어려운듯

 

python3로 채점하자니 시간초과나고

 

import math
from sys import stdin

def get_prime(n):
    
    result = [True]*(n+1)

    for i in range(2,int((n+1)**(1/2))+1):
        
        if result[i]:
            
            for j in range(i+i,n+1,i):
                
                result[j] = False
    
    return result

n = int(stdin.readline())

prime_list = get_prime(n)

answer = 1

for i in range(2,n+1):
    
    if prime_list[i]:
        
        answer *= pow(i,int(math.log(n,i)),2**32)
        answer %= (2**32)

print(answer)

 

그래서 금단의 기술 비트마스크를 이용한 에라토스테네스의 체를 공부해서 해결했다

 

https://deepdata.tistory.com/822

비트마스크를 이용한 에라토스테네스의 체 배우기

 

import math
from sys import stdin

def get_prime_bitmask(n):
    
    result = [255]*((n+1)//8+1)

    result[0 >> 3] &= ~(1 << (0 & 7))
    result[1 >> 3] &= ~(1 << (1 & 7))

    for i in range(2,int((n+1)**(1/2))+1):
        
        if result[i >> 3] & (1 << (i & 7)):
            
            for j in range(i*i,n+1,i):
                
                result[j >> 3] &= ~(1 << (j & 7))
    
    return result

n = int(stdin.readline())

prime = get_prime_bitmask(n)

answer = 1

for i in range(2,n+1):
    
    if prime[i >> 3] & (1 << (i & 7)):
        
        answer *= pow(i,int(math.log(n,i)),2**32)
        answer %= (2**32)

print(answer)

 

c++은 그냥 해도 통과하는것 같던데

 

파이썬의 한계를 느끼기 시작..