[프로젝트 오일러] 문제3 - 가장 큰 소인수

문제

영문

Largest prime factor

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의 소인수 중에서 가장 큰 수를 구하세요.

바로가기

 

해설

파이썬 (Python)

a = 600851475143
i = 2
 
while i <= 775147: #루트 n
  if a%i == 0:   
    if a == i:
      break
    while a%i == 0:
      a = a//i
  i += 1
 
print(i)

위 코드는 다음과 같은 알고리즘으로 동작합니다.

 

1. a는 문제에서 주어진 수, i는 2로 설정한다
2. 만약 a가 i로 나누어진다면, 나누어지지 않을 때까지 a를 i로 나눈 값을 a로 넣는다
3. a가 i로 나누어지지 않는다면, i를 1 증가시킨다
4. 이를 반복하여 a가 i가 되는 경우가 가장 큰 소인수이다!

 

작은 소인수들로 계속 나누어 없애다 보면 마지막에 남아있는 소인수가 가장 큰 소인수일 것이라는 원리입니다! 반복문의 조건은 무한 루프에 빠지지 않도록 설정해둔 것 입니다.

 

C

#include<stdio.h>
int main(void) {
	long long a = 600851475143;
	int i = 2;
	while(i<= 775147){ //루트 n
		if (a%i == 0) {
			if (a / i == 1){
				break;
			}
			a = a/i;
			printf("%d : %lld\n", i, a);
		}
		i++;
	}
	printf("%lld", a);
}

제가 처음에 짰던 코드입니다. 이 코드에는 a 숫자가 바뀔 경우 문제 될 수 있는 부분이 한 가지 있는데, 한번 찾아보세요!

 

정답

6857