[Project Euler]3번문제

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

<풀이>

정말 간단한 방법으로는 1부터 600851475143 숫자를 반복문으로 실행 후 하나씩 소수인지 판단해보면 간단하다 즉 이중반복문을 쓰면 된다. 그러면 대신 시간이 오래걸린다..

그러면 다른 방법은 무엇일까?

1~600851475143의 숫자를 소수인지를 판단후 소수이면 배열에 저장하고

배열에 저장한 숫자로 다 나눠보고 소수가 아닌지 판단하면 좀더 시간이 단축된다. 하지만 소스가 조금 복잡하다 ㅎㅎ

여기까지는 문제가 쉬우니 소스를 올리지 않음

주소 : http://euler.synap.co.kr/prob_detail.php?id=3