프로젝트 오일러 도전기 #3 (with 파이썬 프로그래밍공부)
문제
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
가장 큰 소인수 구하기
어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
1번을 푼 사람들의 절반이 이 문제를 풀지못했다.
갑자기 난이도가 올라갔다는건지 사람들이 포기한건지...
풀이아이디어
소수는 2,3,5,7,11,13 같이 1과 자기자신으로만 나눠지는 숫자다
즉, 나머지가 0이되는 숫자가 1과 자기자신 말고 아무것도 없다는 거다
앞에서 써먹은 %와 for문을 활용하면 이렇게되겠다
1 2 3 4 | for i in range(2,600851475144) : for j in range(2,i): if i%j ==0 break | cs |
예를 들어 8을 확인 했을때
2 3 4 5 6 7 8 을 다 검증할 필요가 없고
2에서 짤라 버리면되기에 break를 넣어주는게 효율적이다.
혹은 divmod를 이용하면 이렇게되겠다
1 2 3 | while 1 : #무한루프 a,b=divmod(x,i) #a는 몫, b는 나머지 if b==0 : #나머지가 0 | cs |
접근법은 3가지정도 떠올랐는데
1. 범위내의 소수를 싹구하고 하나씩 나눠보며 체크한다.
2-1. 범위내 숫자를 하나씩 올려가며 소수 체크를 동시에 진행한다
2-2. 반대로 숫자를 내려가며 소수체크를 동시에 진행한다
-> 글쓰기전에는 이 방법이 가장 합리적이라고 생각했고 이걸로 풀었다.
3-1. 소인수의 성질을 이용해서 큰수에 작은수를 계속 나눠가며 남긴다
100/x
-> x 2에서 나머지 0, 몫50
-> 50/x
-> x 2에서 나머지 0, 몫 25
-> 25/x
-> x 5에서 나머지 0, 몫 5
-> 클리어
3-2
우리가 큰 수를 찾는 문제이기 때문에 이걸 역으로도 한번 생각해보자
100/x
-> x 50에서 나머지 0, 몫 2
-> 50/x
-> x 25에서 나머지 0, 몫 2
-> 25/x
-> x 5에서 나머지 0, 몫 5
-> 클리어
3-1방법은 작은수에서 바로걸러지지만
3-2방법은 100->50까지 내려가야하기에 3-1방법이 더 접근하기 좋을듯하다.
프로젝트 오일러는 목적 자체가 귀납적인 풀이를 해야되기때문에 12번의 방법이 취지에 부합하지만
이번에는 기교를 좀 부려3번의 방법을 이용해보겠다.
만약 2번의 방법으로 100을 구하게된다면
2->100/2 ok
2-> 소수확인 ok
3->no
4-> 100/4 ok
4-> 소수확인 no
...
이런식으로 진행되기에 최소 100번이상의 시행을 겪게되지만
3번방법은 6단계면 끝나버리기 때문이다.
아이디어는 구상을 다했으니 다음단계로 넘어가겠다.
문제풀이
1 2 3 4 5 6 | if b==0 : # b는 나머지 i=1 x=a if i == x : break i+=1 | cs |
클리어
댓글
댓글 쓰기