프로젝트 오일러 도전기 #5 (with 파이썬 프로그래밍공부)

문제

Smallest multiple

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 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

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

무식하게 x를 2~20까지 나눠떨어지는지 체크를 해주는 방식으로 해보자

while 무한 루프에 for 문을 굴려서 체크 카운터를 넣어줘서 쉽게 완성

1 2 3 4 5 6 7 8 9 10

x=1 check=0 while 1:     for i in range(2,21):         if x%i==0 :             check += 1     if check==19 :         break     x+=1     check=0

cs

즉 2에서 20까지 나눴을때 0이되면 (1은 다 가능하니) 

check 가 19가되서 정답이 나오고

그 이외의 경우에는 다시 원점으로 가는것

 

 

 

클리어

 

그런데 time을 넣어서 돌려보니

계산하는데 2276sec... 즉 30분이 넘게 걸린다 ㅋㅋ.....

오늘은 문제를 수학적으로 접근해 보겠다.

1~20사이의 숫자로 나뉜다는 건 다시말해 최소공배수 문제이다.

20까지의 소수를 구하면

2,3,5,7,11,13,17,19 이렇게 8개이다

또한 여러수의 최소공배수를 구하는방법은

2 3 4 5 6 7 -> 2로나눈다

1 3 2 5 3 7 -> 3으로 나눈다

1 1 2 5 1 7 -> 2로 나눈다

1 1 1 5 1 7 -> 5로 나눈다

1 1 1 1 1 7 -> 7로 나눈다

1 1 1 1 1 1 -> 끝

최소공배수는 지금까지 나눈값들을 곱한값이고 

즉, 2x3x2x5x7 = 420

값을 나누고 원본자리에 나눈값을 집어넣어주고

나눈값을 리스트로 빼주면서

원본 리스트의 길이 len(리스트)와

원본 리스트 값들의 합 sum(리스트)의 크기가 같으면 소인수 분해가 완료라는 아이디어에서 착안하여

다시 구문을 짰다

1 2 3 4 5 6 7 8 9 10 11 12 13 14

answer =[] count=0 while 1:     for j in prime :         for i in range(2,len(x)+2) :             a,b=divmod(x[i-2],j)             if b==0 :                 x[i-2]=a                 count+=1         if count>0 :             answer.append(j)             count=0     if count ==0 and sum(x)==len(x) :         break

cs

x는 2~20까지 들어있는 리스트다

 

시간을 측정해보니

 0.00000 sec 

 

거의 바로 계산되었다.

 

추가로 파이썬 math에있는 lcm을 이용하면 문구짤것도 없이 계산된다..