Xzero

Xzero

Mathematics, Coding

Q5_Smallest multiple

들어가기

오늘 살펴볼 문제는 Q5 입니다.
https://projecteuler.net/problem=5

문항해설

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

 1부터 20까지 자연수를 모두 약수로 가지는 가장 작은 자연수를 찾는 문제입니다. 이는 1부터 20까지 자연수의 최소공배수를 찾는 것과 같은 문제입니다.
 그냥 구하려면 1부터 20까지 자연수를 모두 소인수분해하여 각각의 소인수가 몇 개씩 있는지 관찰하여 계산하면 됩니다. 방법은 있지만 계산량이 적지 않아보이네요.
 이 문제는 몇 가지 방법으로 예시코드를 작성해보도록 하겠습니다.

예시코드 1

while True:
    for i in range(1,21):
        if value % i == 0 :
            continue
        else :
            value = value + 1
            break


    else:
        print(value)
        break
# 232792560
  • 120초가 걸립니다. 생각보다 참을성이 필요하네요.
  • value는 우리가 테스트 하는 값이에요. 1부터 하나씩 증가시키면서 원하는 값이 맞는지 테스트해보는 것입니다.
  • i는 1부터 20까지 자연수입니다. value의 약수가 되는지 판단하는 것이죠.
  • continue는 for로 다시 돌아가서 다음 i를 계속(continue)하도록 하는 명령입니다.
  • i로 나눠지는 경우에는 1보다 큰 1에 대해 다시 체크해봐야 하는 것이요.
  • 만약 나눠지지 않는 i가 있다면 for를 끝내고(break) 다른 value에 대해 테스트 해보아야 하지요.
  • 가장 아래의 else를 봅시다. for ~ else의 구문입니다. 이때 else는 for 구문에서 중간에 끝나지 않고(break) for가 끝났을 때 실행되는 구문입니다.
  • 즉, 1부터 20까지의 자연수가 모두 나눠지는 (모두 약수가 되는) value에 대해 실행되고 이때 value를 출력합니다.
  • 그리고 나서 break로 while 문을 종료합니다.
  • 위 코드에서 value = value+1가 없으면 value가 항상 1이므로 무한루프가 걸립니다. 파이썬 창이 끝나지 않는 광경을 목격하게 될거에요.
  • whle 로 반복을 할때는 무한루프가 걸리지 않도록 해야 합니다.
  • 저는 위와 같은 경우에 아래와 같이 itertools.count를 사용하기도 합니다. 이 함수를 사용하면 value = value + 1를 생략할 수 있어요.
import itertools
for value in itertools.count(1):
    for i in range(1,21):
        if value % i == 0 :
            continue
        else :
            break

    else:
        print(value)
        break

#232792560
  • 116초가 걸립니다. 위의 코드와 비슷하게 시간이 많이 걸리네요.
  • 첫 코드와 알고리즘은 같으므로 설명은 생략합니다.

 그런데 역시 수학적인 고찰없이 문제에서 주어진 대로 실행시키니 비효율적입니다. 시간이 많이 걸리지요.

이쯤에서 수학적인 이론을 적용하여 코드를 작성해보도록 합시다.

수학을 넣으면

두 자연수 $a,b$에 대하여 두 수의 최대공약수,최소공배수를 각각 $gcd(a,b), lcm(a,b)$라 하면 다음 식이 성립합니다.

위의 식을 변형하면 다음과 같은 결과를 얻습니다.

또한 세 자연수 $x,y,z$에 대하여 다음 식이 성립합니다.

위를 종합하면 조금은 효율적으로 코드를 구성할 수 있을 것 같습니다.

예시코드2 (수학이론을 적용)

def gcd(a,b):
    while (b!=0):
        r=a%b
        a,b=b,r
    return a
def lcm(a,b):
    return a*b/gcd(a,b)

n=20
c=lcm(1,2)
for i in range(3,n+1):
    c=lcm(c,i)
print(c)
#232792560.0
  • 이 코드는 김쌤이 올려주신 코드입니다.
  • 같은 환경에서 0.04초가 걸렸습니다. !!, 역시 수학의 힘이란!!
  • gcd와 lcm은 각각 주어진 두 수의 최대공약수, 최소공배수를 반환하는 함수입니다.
  • 먼저 1,2의 최소공배수를 구하고, 이 값과 3의 최소공배수를 구합니다. 또한 이때 구한 값으로 4와의 최소공배수를 구해나가는 알고리즘입니다.

마무리

수학이 이렇게 쓸모있는(?) 것입니다!!
같은 내용인데 수학적 이론이 들어가느냐 아니냐에 따라 차이가 크네요.

Leave a Comment