티스토리 뷰

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
37,833
Today
31
Yesterday
37
링크
TAG
more
«   2018/05   »
    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    
글 보관함