[파이썬]프로젝트 오일러 #5

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

최소공배수를 구해보면서 위 사진에 나온것과 같은 규칙을 얻었다. 

n = 20
multiple = 1

a = [False, False] + [True]*(n-1) #소수를 구하는 알고리즘(0~n까지의 배열 체를 만드는 과정)

for i in range(2, n+1):
    if a[i]: #i가 소수라면
        multiple = multiple*i
        primebreak = True
        for k in range(n, 2, -1):
            for l in range(2, n):
                if (k==i**l):
                    multiple = multiple*(i**(l-1))
                    primebreak = False
                    break
            if primebreak == False:
                break
                
        for j in range(2*i, n+1, i): #i의 배수를 체에서 거른다(False로 변환)
            a[j] = False

print(multiple)

'에리토스테네스의 체'로 구현한 코드를 사용하여 소수(변수:i)를 구하였다.

소수를 구했을 때 그 소수를 거듭제곱 해서 구할 수 있는 수가 존재하는지를 알아보기 위하여 변수k와 l을 사용하여 가장 큰 소수의 거듭제곱 수를 구해주었다. 

이중 반복문을 빠져나가기위해 break를 두번을 써주었는데, primebreak = True라고 설정해서 l의 반복문을 빠져나오면 False로 바꿔주고, 나머지 반복문도 빠져나가도록 해주었다. 

 

primebreak = True를 써주는 위치에 따라서 다음 소수에서 거듭제곱수를 구하는 반복문이 실행이 안될 수 도 있어서 주의해줘야한다...

 

답: 232792560