Blog Full Notice
back to main page
프로젝트 오일러 문제 5. 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는. 네이버 블로그
motivation: 네이버 블로그
#프로젝트 오일러 문제 5: 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는? : 네이버 블로그
프로젝트 오일러 문제 5: 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는?
무지성
・
2021. 7. 23. 23:59
#problem5
'''1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?'''
def numcandivide(num,dividenum):
if num%dividenum==0: return True
else: return False
def findanswer(num,givennumber):
for i in range(1,1+givennumber):
if numcandivide(num,i)==False: return False
j=1
while True:
if findanswer(j,19)==None: break
j+=1
print(j)
답: 232792560
문제 푸는데 55분 걸렸다.
구문 실행 시간은 약 5분이었다. 5분은 너무 시간이 많이 걸린 것 같아서 내일 한번 더 다른 코드로 답을 구해볼 것이다.
-그 다음날-
#problem5_try2
'''1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?'''
#n이 소수면 자기 자신을 출력, 소수가 아니면 0을 출력하는 prime함수
def prime(n):
result=0
for i in range(1,n):
if n%i==0: result+=1
if result==1:
return n
else: return 0
#모든 소수가 들어있는 리스트 생성(20까지)
list=[]
for i in range(2,20):
if prime(i)!=0: list.append(prime(i))
#list 변수들이 key, '0'이 value가 되는 딕셔너리 생성
a=dict(zip(list,(('0 '*len(list)).split())))
#숫자 n에 대한 소인수 모음집(딕셔너리) 생성하는 factorization(n) 함수
def factorization(n):
factorizationdict=a.copy()
for i in list:
k=0
while n>=i:
if n%i!=0:
break
else:
n=n/i
k+=1
factorizationdict[i]=k
return factorizationdict
#dict1, dict2의 공통 인수 딕셔너리 생성하는 commonfactor 함수
def commonfactor(dict1,dict2):
dict3=dict()
for i in range(len(list)):
if int(dict1[list[i]])>=int(dict2[list[i]]): dict3[list[i]]=int(dict1[list[i]])
else: dict3[list[i]]=int(dict2[list[i]])
return dict3
#1부터 20까지로 나눌 수 있는 수의 소인수 딕셔너리
k=factorization(1)
for i in range(1,21):
k=commonfactor(k,factorization(i))
#딕셔너리를 통해 구한 최종 숫자
answer=1
for i in range(len(list)):
answer=answer*list[i]**k[list[i]]
print(answer)
똑같은 답이 나왔지만 컴퓨터가 답을 구하는 속도는 굉장히 빨랐다.
댓글남기기