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를 먼저 체크
2. '2'를 제외한 나머지 소수들은 전부 3 이상이며 홀수이다.
따라서 2를 제외한 소수들은 2n+1 이라는 공통적인 속성을 갖는다.
3. 소인수 분해를 계속해서 진행하면 결국 마지막 소수로 나눌때는 몫이 0이 된다.
숫자가 마지막 소수의 여러번의 거듭제곱으로 이루어져 있어도 결국 몫은 0이다.
4. 나누어 떨어지면 현재의 소수를 유지하고 나누어 떨이지지 않으면 + 2를 한다. ( 2번의 이유때문에 )
C / C++
unsigned __int64 number = 600851475143;
while ( number % 2 == 0 ) number /= 2;
int prime = 3;
while ( number / prime != 0 )
(number % prime) == 0 ? number/=prime : prime+=2;
cout << "Question 3 : " << prime << endl;
