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

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

 

문제풀이

제가 생각한 풀이

LCM(( 1,...,n ))을 구하는 문제입니다. 

수학문제인데 어떻게 해결할수 있을까를 생각해보니

LCM(( 1,..,n ))을 소인수분해한다면 2^a * 3^b * 5^c * 7^d... (( 0<=a,b,c,d ))

이 나올것입니다.

결국 어떤 형식이 되냐면, p(( 소수 )) p^k<=N형식으로 나올것입니다.

예를 들자면 LCM(( 1,2,..,10 ))=2^3 * 3^2 * 5^1 * 7^1

그럼 우리는 N이하의 소수를 구하고 각 소수마다 올바른 k를 구하고 답에 곱하면 될것입니다.

 

하지만..

에라토스테네스의 체를 구현하면 N=10^8이면 느린 파이썬으로 시간초과가 나올게 뻔하니 pypy로 했었는데 이게 뭐람..

def main():
    N=int(input())
    prime=[False]*(N+1)
    mod=4294967296
    ans=1
    while ans*2<=N:ans*=2
    i=3
    for p in range(3,int(N**0.5)+1,2):
        if not prime[i]:
            c=i
            while c*i<=N:c*=i
            ans=ans*c%mod
            for j in range(i*i,N+1,i*2):
                prime[j]=True
        i+=2
    for i in range(i,N+1,2):
        if not prime[i]:
            ans=ans*i%mod
    print(ans)
                
main()

MLE??? 아마도 False배열을 10^8을 하니 MLE를 받은것 같았습니다. 그래서 메모리를 효율적으로 하는 방법이 있나 하고 찾아봤는데

다행이게도 파이썬 내장함수/클래스 중에서 bytearray라는게 있었습니다. 배열의 내용을 바이트로 저장해서 효율적으로 저장할수 있다는것을 알았습니다. 자세한내용은 공식문서 참고( https://docs.python.org/ko/3/library/stdtypes.html#bytearray )

그래서 AC를 받았습니다!!

def main():
    N=int(input())
    prime=bytearray(N+1) #소수배열을 바이트 배열로 선언
    ans=1
    while ans*2<=N:ans*=2
    i=3
    for p in range(3,int(N**0.5)+1,2):
        if not prime[i]:
            c=i
            while c*i<=N:c*=i
            ans*=c
            ans&=(1<<32)-1
            for j in range(i*i,N+1,i*2):
                prime[j]=1
        i+=2
    for i in range(i,N+1,2):
        if not prime[i]:
            ans*=i
            ans&=(1<<32)-1
    print(ans)
                
main()

그리고 다른분들은 어떻게 푸셨는지 궁금해서 코드를 보니 비트마스킹으로 푸신분들도 많아서 다른 선생님들이 비트마스킹으로

푸신 코드로 비트마스킹도 같이 공부할겸 메모리를 효율적으로 사용하는 에라토스테네스의 체도 같이 알아보겠습니다.

비트마스킹 풀이

anfidthtn님의 정답코드를 바탕으로 적었습니다.

( 코드는 제 코드가 아니므로 올리지않음. )

제 풀이보다 거의 3배나 절약한 메모리 (2번째분 풀이도 비트마스킹입니다.)

1. 소수를 마킹할 리스트를 만든다.

메모리를 줄이기위해 홀수만 저장하는 배열을 비트마스킹으로 저장한다.

32비트를 n//64 +1 개의 리스트를 만드는데 각 인덱스에는 32개의 홀수를 저장한다. (( 32비트 생성 ))

예를 들면 67은  1번 인덱스의 1번 비트 / 5는 0번 인덱스의 2번 비트에 저장 이렇게

초기에는 모두 1(( true ))상태로 초기화

 

2. 체를 돌린다. 해당수가 소수인지 합성수인지 확인하는 방법은 먼저 해당수가 소수배열의 몇번 인덱스 인지 구하고 i//64( i>>6 ) 그곳에서 

몇번째 인덱스 홀수인지 구하고 i//2((i>>1)) 숫자가 그 비트의 몇번째 인지 구하고 (( i>>1 ))&31 그 비트를 따라가면 된다 (( 1<< ))

만약 그 비트의 값이 0이면 이미 합성수로 마킹된거고 아니면 소수인거다.

예시) i=67 67//64=1, 1번 인덱스의 (( 67//2 ))&31=33&31=

00000000 00000000 00000000 00100001(( 2 ))&00000000 00000000 00000000 00011111( (2 ))= 00000000 00000000 00000000 00000001(( 2 )) 이므로 1번비트가 67이 소수인지 아닌지를 판명한다. 1이면 소수 0이면 합성수로 나타날것이다.

3. 합성수를 마킹한다.

ex)8비트로 가정하고 

00010000 으로 5번째 비트를 찾아서 o, x 여부를 봤다면
        이번엔
        11111111
        00010000 을 xor 해서
        11101111 을 만든 다음
        int와 &을 해서 나머지는 유지하고 해당 자리 비트만 0으로 만듦

- 코드의 주석

예시로 7의 배수를 마킹한다고 하고, N=45으로 하겠습니다.

i=7 n=45

첫번째 루프:

j=21

7//64=0번 인덱스에서

11111111 11111111 11111111 11111111_{(( 2 ))} XOR 00000000 00000000 00000100 00000000_{(( 2 ))} [21 비트 위치]

=11111111 11111111 11111011 11111111_{(( 2 ))} 가 될것이고

7까지는 초기화 상태 그대로 이므로

11111111 11111111 11111111 11111111₍₍₂₎₎&11111111 11111111 11111011 11111111_{(( 2 ))} = 11111111 11111111 11111011 11111111_{(( 2 ))} 가 됩니다. 이를 n+1까지 반복하되 i*2만큼씩만 j를 띄어서 해주면 됩니다.

이렇게 합성수를 체크하면서 하면 메모리를 절약을 엄청할수 있고 시간도 나름?최적화 되는것 같았습니다.

회고

에라토스테네스의 체를 사용하는데 어떻게 하면 효율적으로 풀수 있을까 및 메모리관리의 중요성에 대해 다시 한번 깨닫게 되었고,

비트마스킹에 대해서 더 자세하게 알수있고 공부하는 계기가 되었습니다.

 

태그

#정수론 #수학 #소수판정 #에라토스테네스의 체 #비트마스킹