Problem3. What is the largest prime factor of the number 600851475143 ?
번역: 600851475143 를 나누었을 때, 나누어 떨어지는 수 중 가장 큰 소수(Prime number)는 ?
직관적으로 풀면...
해당 숫자의 제곱근 부터 차례로 1씩 감소 하면서..
해당 숫자를 나눌 수 있는지..
소수인지 확인하면 됩니다.
주어진 숫자가 좀 커서 int 범위로 포함진 않습니다.
다행이 제곱근은 int 범위에 있습니다.
#light
let target_number = 600851475143UL;
let max_candidate = (int (sqrt (float target_number)))
let is_prime i =
[2 .. i-1]
|> Seq.exists (fun x -> i%x = 0)
|> not
let is_factor_of x =
target_number%(uint64 x) = 0UL
[max_candidate .. -1 .. 2]
|> Seq.filter is_factor_of
|> Seq.filter is_prime
|> Seq.hd
|> printfn "Problem #3 = %d"
가장 큰 수부터 검사하기 때문에 head를 찍으면 됩니다.
참고로... is_factor_of 와 is_prime 의 줄을 바꾸면
Performance 는 끔찍해집니다.
-----------------
좀 비 직관적이지만...
let rec find_last_prime_factor (n: uint64) (i: uint64) (result: uint64) =
if (n <= 1UL) then
result
else
if (n % i = 0UL) then
(find_last_prime_factor (n/i) i i)
else
(find_last_prime_factor n (i+1UL) result)
find_last_prime_factor target_number 2UL 0UL
|> printfn "Problem #3 = %d"
이렇게 풀 수도 있습니다.
'내 생산물' 카테고리의 다른 글
| F#, Project Euler - Problem #20 (0) | 2009/05/12 |
|---|---|
| F#, Project Euler - Problem #5 (0) | 2009/05/11 |
| F#, Project Euler - Problem #4 (2) | 2009/05/11 |
| F#, Project Euler - Problem #3 (0) | 2009/05/10 |
| F#, Project Euler - Problem #1 (2) | 2009/05/10 |
| F#, Project Euler - Problem #2 (0) | 2009/05/10 |
| 테터 데스크 설치 - 미투데이 최근글 표시하기. (2) | 2007/06/11 |
