Blog Full Notice
back to main page
프로젝트 오일러 문제 3 600851475143의 소인수 중에서 가장 큰 수를 구하세요. 네이버 블로그
motivation: 네이버 블로그
#프로젝트 오일러 문제 3: 600851475143의 소인수 중에서 가장 큰 수를 구하세요. : 네이버 블로그
프로젝트 오일러 문제 3: 600851475143의 소인수 중에서 가장 큰 수를 구하세요.
무지성
・
2021. 7. 17. 0:14
#problem3.py
'''어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고,
이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.'''
#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
#모든 소수가 들어있는 리스트 생성(10000까지)
list=[]
for i in range(2,10000):
if prime(i)!=0: list.append(prime(i))
a=600851475143
j=0
while True:
if a%list[j]==0:
a=a/list[j]
if a<list[j]: break
if a%list[j]!=0:
j+=1
print(list[j])
답: 6857
처음에는 이렇게 해서 정답을 맞췄는데
정답을 맞추고 다른 사람의 풀이를 보니까 굳이 소수(prime number) 리스트를 만들지 않아도 되더라구요..
하..진짜 현타가 제대로 오는데요
그래서 정석 풀이로 다시 한번 만들어 보겠습니다.
#problem3_renewed.py
'''어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고,
이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.'''
i=2
a=600851475143
while True:
if a%i==0:
a=a/i
if a<i: break
if a%i!=0:
i+=1
print(i)
이렇게 하니까 답도 순식간에 나오네요..
제 머리가 나쁜 것을 탓해야지 무엇을 탓하겠습니까ㅋㅋㅋ
혹시 이 코드도 별로 안 좋은가요?
사실 지금은 비전공자라 아무것도 몰라서 예쁜 코딩? 좋은 코딩?이 뭔지 잘 몰라서..
개선할 점 알려주시면 감사하겠습니다ㅋㅋㅋ
+P.S.
그리고 앞으로 문제 풀때는 타이머를 제놓고 풀어야겠습니다.
이 문제는 한 2시간 걸린 것 같습니다ㅋㅋㅋ
근데 좋은 점은 이제는 문제를 어떻게 접근해야 하는지 감이 조금은 잡힌 것 같네요
약간 무지성으로 풀지 말고 먼저 생각을 하고 풀어야 된다는 것을 알게 되었습니다ㅋㅋㅋㅋ
+알게된 점
a=[0,1,2,3,4,5,6,7,8,9,10]
print(len(a))
>>>11
print(a[::-3])
>>>[10,7,4,1]
print(a[::3])
>>>[0,3,6,9]
댓글남기기