003. Largest Prime Factor (어떤 수에 대한 가장 큰 소인수 구하기)

​문제 (English)

The prime factor of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of number 600851475143?

 

Answer: 6857

문제 분석

---

가장 큰 소인수를 찾는 문제이다. 

 

일견 생각할 때, 주어진 수보다 작은 소수를 에라토스테네스의 체(Eratosthenes Sieve)를 이용해서 모두 찾아내고, 이 소수 중 큰 값부터 해당 수의 약수인지 비교하면서 찾을 수도 있을 것처럼 보인다. 그러나, 문제에서 주어진 600851475143보다 작은 모든 소수를 찾으려면, 이 크기만큼의 배열 혹은 벡터를 선언한 후 찾아야 하는데, 대략 600G Bytes의 메모리를 차지해서, 메모리 오버플로우가 발생한다. 즉, 계산이 안된다.

 

따라서, 다른 방법을 찾아봐야하는데, 중학교 때 배웠던 방법인, 주어진 수를 2부터 나눠가면서, 나눠지지 않을 때는 그다음 수인 3으로 나눠가면서 몫이 1이 될 때까지 나눠보는 방법을 사용하면 된다.

1) n = p*q + r 에서, p를 2에서부터 r==0일 때까지 증가시키면, 이때 p는 첫 번째 소수가 된다.

2) 1번에서의 q를 n으로 놓고, 다시 p=2에서 부터 r==0일 때까지 p를 계속 증가시킨다.

3) q==1이 되면, p가 n/2보다 큰 수가 되는것이기에 break

4) 답은 n이 된다. 

 

n=12일 때를 예로 들어보자. 즉, 12의 가장 큰 소인수를 찾는 것.

$n=pq+r$에서 p=2일 때 r=0이 되고, 이 때 q=6이다.

이제 n=6으로 놓고 $6=pq+r$에서 r==0일때를 찾아보면 p=2, q=3일 때 r=0이 된다. 

다시 n=3으로 놓으면 $3=pq+r$에서, p=3, q=1일 때 r=0이 된다. (p=2의 경우는 만족하는 q가 없어서, p를 1 증가시킨 3으로 시도해 보게 됨)  

 

 

n=10일 때는 아래와 같이 된다.

 

풀이 1 

코드는 다음과 같다.

1)$n=qp+r$에서 루프 진입

2) (q,r)=(n/p,n%p)를 구하고,

3) 만약 q=1이면 break

4) r=0이면 n=q로 놓고 루프 계속, r!=0이면 p를 증가시키고 루프 계속

5) q=1에 의해 루프가 종료되면, 이때의 n값이 가장 큰 소인수

 

소스는 아래와 같다. 

fn find_answer(mut n:u64) -> u64{   
    let mut p = 2;
    let mut q;
    let mut r;
    loop{        
        (q, r) = (n/p, n%p);        

        if q==1 { break;}

        if r == 0 { n = q;  }
        else      { p += 1; }      
    }
    return n;
}

 

이 풀이로도 작은 수일때는 잘 동작하지만, 매우 큰 수에 대해서는 hackerrank에서 타임아웃이 발생한다. 

풀이 2 

---

풀이1은 매우 큰 값에 대해서는 타임아웃이 발생한다. 좀 더 수행시간이 짧게 하기 위해서는 어떻게 해야 할까?

두 가지 제약조건을 둬서, 수행시간을 줄여보자.

1) 루프 안에서 (q, r) = (n/p, n% p)를 무조건 수행 후 q와 r의 값을 체크했는데, r=0의 경우만 n/p를 수행하게 하자

2) p의 값은 sqrt(n) 미만까지만 수행해도 되도록 하자.

 

먼저 1번은 간단하다. 

fn find_answer1(mut n: u64) -> u64{    
    let mut p = 2;    
    while n > 1 {
        if 0 == n%p { 
            n /= p;             
        }
        else { p +=1; }        
    }
    if n != 1 { p = n;}
    return p;
}

 

위 1번에 의해서 약간 수행시간이 줄지만, 크게 개선되진 않는다. 

2번의 sqrt(n) 미만까지만 p를 수행하게 해야, 크게 개선된다.

fn find_answer2(mut n: u64) -> u64{    
    let mut p = 2;
    let mut max_factor:u64 = (n as f64).sqrt() as u64;
    while n > 1 && p <= max_factor{
        if 0 == n%p { 
            n /= p; 
            max_factor = (n as f64).sqrt() as u64;
        }
        else { p +=1; }        
    }
    if n != 1 { p = n;}
    return p;
}

 

sqrt(n) 보다 큰 값이 p, q에 대해서는 항상 pq > n이 되기에, p <= sqrt(n)까지만 검사해 봐도 된다.

 

예를 들어보자. n=11에 대해서 그냥 계산해 볼 때와, sqrt(n) 보다 작은 p에 대해서만 계산하는 것을 비교해 보자.

동일하게 답을 찾아내고 있으나, 계산량은 현저하게 줄어드는 것을 알 수 있겠다.

 

풀이 3

---

풀이 2까지만 하더라도 hackerrank를 통과할 수 있을 정도로 빠르다.

 

여기에 좀 더 빠르게 해 보자. 

1) 2에 대해서 나눌 수 있는데 까지 나눈다. 

2) 3부터 시작해서 소인수를 구해 보는데, 1번에서 2에 대해서 나눌 수 있는 데까지 나눴기에 2씩 증가시키면서 소인수를 구해도 된다.

 

코드는 아래와 같다.

fn find_answer3(mut n: u64) -> u64{    
    //2에 대해서 처리
    let mut last_factor:u64 = 2;
    if n % 2 == 0 {
        n /= 2;
        while n % 2 == 0 { n /= 2; }
    }else {
        last_factor = 1;
    }

    //3이상 소인수 처리
    let mut p:u64 = 3;
    let mut max_factor:u64 = (n as f64).sqrt() as u64;
    while n > 1 && p <= max_factor{
        if 0 == n%p { 
            n /= p; 
            last_factor = p;
            max_factor = (n as f64).sqrt() as u64;
        }
        else { p +=2; }     //2씩 증가   
    }

    if n != 1 {last_factor = n;} 

    return last_factor;
}

 

총평

---

n=pq+r에 의해 소인수를 구하는 방법과, sqrt(n)까지의 수에 대해서만 p를 구하는 것이 핵심 

 

전체 소스코드

---

p3.rs 

#[test]
fn test(){
    assert_eq!(5, find_answer(10));
    assert_eq!(2, find_answer(16));
    assert_eq!(17, find_answer(17));

    assert_eq!(29, find_answer(13195));
    assert_eq!(6857, find_answer(600851475143));
}

#[cfg(test)]
/// 알고리즘 설명
/// 1) n = p*q + r 에서, p를 2에서부터 r==0일때까지 증가시키면, 이때 p는 첫번째 소수가 된다.
///     (초등학교때 배운 소인수분해 방법)
/// 2) 1번에서의 q에 대해 다시 소인수 분해하면되기에 n=q로 놓고 r==0일때까지 p를 계속 증가시킨다.
///   - 이때 p는 위 1번에서 증가시키던 p값을 이어받아 계속 증가시킨다.///   
/// 3) q==1이 되면, p가 n/2보다 큰 수가 되는것이기에 break
fn find_answer(mut n:u64) -> u64{   
    let mut p = 2;
    let mut q;
    let mut r;
    loop{        
        (q, r) = (n/p, n%p);        

        if q==1 { break;}

        if r == 0 { n = q;  }
        else      { p += 1; }      
    }
    return n;
}


//-----------------------------------------
#[test]
fn test1(){
    assert_eq!(5, find_answer1(10));
    assert_eq!(2, find_answer(16));
    assert_eq!(17, find_answer1(17));

    assert_eq!(29, find_answer1(13195));
    assert_eq!(6857, find_answer1(600851475143));
}

#[cfg(test)]
/// 
/// find_answer1과 동일한 알고리즈 구조인데, 코드를 좀 더 단순화 시킨 버전
///   - 알고리즘1은 항상 q를 계산했는데, 알고2에서는 n%p==0의 경우만 계산 -
fn find_answer1(mut n: u64) -> u64{    
    let mut p = 2;    
    while n > 1 {
        if 0 == n%p { 
            n /= p;             
        }
        else { p +=1; }        
    }
    if n != 1 { p = n;}
    return p;
}

//-----------------------------------------
#[test]
fn test2(){
    assert_eq!(5, find_answer2(10));
    assert_eq!(2, find_answer(16));
    assert_eq!(17, find_answer2(17));

    assert_eq!(29, find_answer2(13195));
    assert_eq!(6857, find_answer2(600851475143));
}

#[cfg(test)]
/// max_factor가 sqrt(n)보다 작은 범위에서만 계산하도록 함 
fn find_answer2(mut n: u64) -> u64{    
    let mut p = 2;
    let mut max_factor:u64 = (n as f64).sqrt() as u64;
    while n > 1 && p <= max_factor{
        if 0 == n%p { 
            n /= p; 
            max_factor = (n as f64).sqrt() as u64;
        }
        else { p +=1; }        
    }
    if n != 1 { p = n;}
    return p;
}

//-----------------------------------------
#[test]
fn test3(){
    assert_eq!(5, find_answer3(10));
    assert_eq!(2, find_answer(16));
    assert_eq!(17, find_answer3(17));

    assert_eq!(29, find_answer3(13195));
    assert_eq!(6857, find_answer3(600851475143));
}

#[cfg(test)]
/// p의 증가를 빠르게
fn find_answer3(mut n: u64) -> u64{    
    //2에 대해서 처리
    let mut last_factor:u64 = 2;
    if n % 2 == 0 {
        n /= 2;
        while n % 2 == 0 { n /= 2; }
    }else {
        last_factor = 1;
    }

    //3이상 소인수 처리
    let mut p:u64 = 3;
    let mut max_factor:u64 = (n as f64).sqrt() as u64;
    while n > 1 && p <= max_factor{
        if 0 == n%p { 
            n /= p; 
            last_factor = p;
            max_factor = (n as f64).sqrt() as u64;
        }
        else { p +=2; }     //2씩 증가   
    }

    if n != 1 {last_factor = n;} 

    return last_factor;
}

 

끝