티스토리 뷰

Project Euler

프로젝트 오일러

 

Problem 3

소인수 중 가장 큰 수 구하기

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를 들면 13195의 소인수는 5, 7, 13, 29입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.


Hint

소인수분해 이론을 이용하여 풀 수 있음!


소인수분해 Example

60을 소인수분해하면?!


먼저 2로 나누어본다.

60 / 2 = 30 ... 0   --> 나머지가 0이므로 소인수에 추가!   60 = 2 X 

30 / 2 = 15 ... 0   --> 나머지가 0이므로 소인수에 추가!   60 = 2 X 2 X

15 / 2 = 7 ... 1    --> 15는 2로 나누어떨어지지 않으므로 2로 나누기 끝.


그 다음 3으로 나누어본다.

15 / 3 = 5 ... 0   --> 나머지가 0이므로 소인수에 추가!   60 = 2 X 2 X 3 X

5 / 3 = 1 ... 2    --> 5는 3으로 나누어 떨어지지 않으므로 3으로 나누기 끝.


그 다음 4로 나누어본다.

5 / 4 = 1 ... 1   --> 5는 4로 나누어 떨어지지 않으므로 5로 나누기 끝.


그 다음 5로 나누어본다.

5 / 5 = 1 ... 0   --> 5는 5로 나누면 나누어 떨어지고, 몫이 1이므로 소인수분해 끝.

                    --> 나머지가 0이므로 소인수에 추가!    60 = 2 X 2 X 3 X 5


결과적으로 60 = 2 X 2 X 3 X 5

소인수는 2, 3, 5! 소인수분해 끝!


Answer

출력 답 : 6857


소수 중 2를 제외한 나머지는 홀수라고 합니다.

그래서 2와 나머지 홀수를 처리하는 코드를 분리하였습니다.






댓글
댓글쓰기 폼
공지사항
Total
41,170
Today
70
Yesterday
59
링크
TAG
more
«   2018/07   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함