Problem 3
출제 일시 : 2012-01-03 19:11:35
어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
원래는 에라토스테네스의 체를 사용하여 풀려고했으나 범위가 너무 많았다.
파이썬은 사용하기 귀찮아서, 풀이를 살짝 엿보고 풀었다.
그냥 1은 무조건 아니니 2부터 number와 나누어떨어지는게 있다면 소수후보로 넣는다.
그다음에 또 같은 숫자로 나누어질 수 있으니 while문으로 계속 나눠준다 // 핵심
그리고 number의 소인수중 1개를 찾았으므로, number를 나누어준다.
그 인수만 뺴고 생각하겠다는 것이다.
그리고 for문의 종료조건은 number가 1보다 큰걸로 해야한다.
number는 언젠가 1까지 내려가기 때문인데, 만약 j<number이렇게 주면
number가 1까지 내려가기도 전에 종료가 되어서 값보다 한참 적은 녀석이 출력될 것이다.
#include <bits/stdc++.h>
using namespace std;
int main(){
long long int number = 600851475143;
long long int i = 1;
for(long long int j=2; 1<number; ++j){
if( ( number%j )==0 ){
i = max(i,j);
while(( number%j )==0){
number/=j;
}
}
}
cout<<i;
return 0;
}
