ProjectEuler 3

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의 가장 큰 소수인 약수는 무엇인가

 

 

코드는 다음과 같다

public static void main(String[] args){
		long target = 600851475143L;
		long ans = find_P(target);
		System.out.println(ans);
	}
	
static int find_P(long target){
	long buf = target; 
	int ans=2;
	
	while(buf > ans){
	    if(buf % ans == 0){
	        buf = buf/ans;
	    }
	    else{
	        ans++;
	    }
	}
	return ans;
}

 

이 문제를 푸는데 핵심은 BruteForce 방법을 이용하지 않고 문제를 풀 수 있느냐를 물어보는 것 같다

(혹시나 BruteForce를 사용한다고 해도 설마 loop의 range를 주어진 수 전체로 두지는 않겠지...?

소수인 약수는 는 주어진 수의 0.5배를 넘을 수 없다! 

예를 들어 주어진 수가 10이라 하면 5이상의 소수는 절대 10의 약수가 될 수 없다는 것을 바로 알것이다)

 

1~5번째 줄은 main method를 돌리는 거라 크게 볼건 없고

 

7~20번째 줄까지 살펴 보면 된다 

 

8번째 줄에서 'target' parameter를 buf 로 복사하는 이유는 Call by value 형식으로 변수가 넘어오기 떄문이기도 하고

주어진 수를 소수인 약수로 계속하여 갱신하기 때문이다

 

9번째 줄의 'ans' 변수는 소수를 저장하는 변수이다 

 

11번째 줄에서는 buf가 ans보다 클 경우 안의 코드를 실행하는데,

ans는 계속 늘어나는 소수이고, buf는 ans로 나눠지지 않을 때까지 나눠지는 수이기 때문에

마지막에 최종 제일 큰 소수가 ans에 할당되면 while문을 탈출하게 된다. 

 

12번째줄의 if 문에서 만약 ans로 buf를 나눌수 있으면 buf를 나눈다

그렇지 않으면 15번째 줄 else문에서 ans를 증가시킨다

 

여기서 포인트는 어떠한 수이던 간에 소수인 약수는 단 한번밖에 나오지 않기 때문에 이런식으로 값을 구할 수 있다. 

예를들어 81이라는 숫자는 3의 4승인데, 3이 4번 곱해져서 그렇지 소수인 약수는 3밖에 없다,

 

위 코드는 일종의 제일 큰 수를 저장하는 기능이 있는 소인수 분해코드라고 보면 된다.