개발하는 TeEm0

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밖에 없다,

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

2번문제

Each new term in the Fibonacci sequence is generated by adding the previous two terms. 
By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
find the sum of the even-valued terms.

해석 : 

피보나치 수열의 다음 수열은 이전의 두 수열을 더한 합과 같다

1과 2로 시작하여 처음 10번째까지의 수열은 다음과 같다:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89

4백만이 넘지 않는 피보나치 수열이 있다고 가정할때 

짝수인 피보나치의 수열을 합을 구하여라

코드는 아래와 같다 

     public static void main(String []args){
        int sum = 0;
		int f1 = 1;
		int f2 = 1;
		while(f1<4000000){
			f1 = f1 + f2;
			f2 = f1 - f2;
			if(f1%2==0){
				sum=sum+f1;
			}
		}
		System.out.print(sum);
     }

문제가 물어보는 것은 피보나치 수열을 짤 수 있느냐를 물어보는 것 같다. 

int buf =0;
int f1 = 1;
int f2 = 1;
	while(true){
		buf = f2;
		f2 = f1+f2;
		f1 = buf;
	}

1번째 줄은 임시 변수

2번째 줄의 f1은 피보나치 첫번째 수열인 1
3번째 줄의 f2는 피보나치 두번째 수열인 1이고

나머지는 일반적으로 간단하게 생각할 수 있는 변수를 3개를 사용하여 계속해서 피보나치 수열을 만들어가는 방법이다

(코드는 돌리지 마시길.. 무한 루프임ㅋㅋ)

하지만 조금 생각해보면 만들어질 새운 피보나치 수열은 현재 변수 2개로 만든다!

int f1 = 1;
int f2 = 1;
	while(true){
		f1 = f1 + f2;
		f2 = f1 - f2;
	}

위 코드를 잘 보면

4번째 줄에서 하는 작업은 피보나치의 다음 수열을 현재 두개의 변수로 생성한다

이게 핵심인데 피보나치 수열을 이항하면 F[n-1] = F[n] - F[n-2]와 같은 식이 나오는데

피보나치의 다음수열에서 이전전 수열을 빼면 이전 수열이 나온다는 소리이다. 

4번째줄에서 f1변수는 F[n]을 저장하였고 f2변수는 F[n-2]를 저장하고 있기 때문에 둘이 빼면 F[n-1]을 얻을 수 있다!!!

말로 설명하니까 햇갈릴수도 있는데, 직접 수를 대입해서 몇번만 해보면 이해갈것이다. 

문제 조건이 짝수인 피보나치인 수를 더하는 것이기 때문에 mod operation으로

홀수를 걸러주면서 더해주면 답이 나온다!

1번문제이다

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

해석하자면 다음과 같다

만약 10 이하의 자연수 중에서 3과 5의 배수를 나열한다면 3,5,6,9 가 될것이고, 이들의 합은 23이다

1000이하의 수에서 3과 5의 배수들의 합을 구하여라 

코드는 아래와 같다 

package Euler;

public class Euler1 {
	public static void main(String[] args){
		int a = 0;
		for(int i = 0; i<=1000; i++){
			if(i%3==0||i%5==0){
				a = a+i;
			}
		}
		System.out.print(a);
	}
}

이 문제의 핵심은 3과 5의 공배수인 15의 배수의 처리를 어떻게 할것이냐를 물어보는 것 같다. 

15를 2번 더하지만(3에서 한번 5에서 한번) 않으면 쉽게 풀 수 있다. 

그냥 진짜 프로그래밍의 기초를 물어보는 것 같은 문제이다 

코드설명 : 

5: a 는 3과 5의 배수를 더하기 위한 변수

6: 0 ~ 1000까지 

7: 만약 i가 3이나 5로 나누어 떨어질경우 

8: 그 수를 더한다