1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

사이트 이름 - 문제 5번

• 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

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

해결방법

어떤 수가 들어왔을 때 2부터 10까지 모두 나눠보고 떨어지는 수를 찾으면 될거같다. 그렇다면 while문으로 무한루프를 돌리다가 해당 값이 나오면 break 거는 방식으로...하니 안된다.😁

그래서 다시 아래처럼 약수리스트 개수만큼만 루프 돌리는 방식으로 바꿨다.

measures = [i for i in range(2, 21)]

number = 10

'''
리스트 안에 있는 원소들을 모두 나눠봐야 하기 때문에
무조건 리스트의 개수만큼 루프 돌아야 함
'''
cnt = len(measures) # 리스트의 개수
i = 0
while i < cnt:
    '''
    하나라도 나누어 떨어지지 않는다면 숫자를 1 증가시키고
    i 는 0으로 초기화 한다.
    그리고 다시 처음부터 반복한다.
    '''
    if number % measures[i] != 0:
        number += 1
        i = 0
        continue
    else:
        i += 1
        if i == cnt:
            print(number)

'''
답 : 232792560
수행속도가 엄청 느리다.ㅠㅠ
'''

해설

• 최소공배수(least common multiple)

• 위키백과, 최소공배수

여러 개의 정수의 공배수는 그들 모두의 배수가 되는 정수이다. 최소공배수(Least Common Multiple, LCM)는 양의 공배수 가운데 가장 작은 하나이다.

여러 개의 정수 n1,n2,…,nk∈Z:nk≠0의 최소공배수 lcm{n1,n2,…,nk}는 재귀적으로 lcm{lcm{n1,n2,…,nk−1},nk}로 정의할 수 있다.

다른이의 해결법

왜 이렇게 되는지 아직 이해를 못하겠다. 중학교 수학시간에 나왔다는데 졸았었나???😑

def Solution(range):
  count = 1
  i = 1
  num = 1

  while count <= range:
    if i <= range:
      if num % i == 0:
        print(i)
        count += 1
        i += 1
        print('pass')
      else:
        if i % 2 == 0:
          num = num * 2
          count = 1
          i = 1
        elif i % 3 == 0:
          num = num * 3
          count = 1
          i = 1
        elif (i % 5) % 5 == 0:
          num = num * 5
          count = 1
          i =1
        elif (i % 7) % 7 == 0:
          num = num * 7
          count = 1
          i = 1
        else:
          num = num * i
          count = 1
          i = 1
        print('reset')
    if count == range + 1:
      print(num)
      break

Solution(20)