Lesson 10. Prime and composite numbers - CountFactors #3 (속도 개선-2)

(CountFactors #2)에서 100%가 안된 이유가 무엇일까? 

알고리즘의 개선이 필요하다기 보다는, 약간의 코드 최적화가 필요하다.

 

아래 코드에서는 while(조건문)을 수정했다.

#include <cmath>

int solution(int N) {

    int cnt = 0;
    int i = 1;
    
    //while(i * i < N)
    while(i < sqrt(N))
    {
        if(N % i == 0) cnt +=2;
        i++;
    }

    if(i * i == N) cnt++;

    return cnt;
}

 

이전 코드의 조건문은 N과 비교하기 전, 항상 \( i \times i \) 연산이 필요했다.

변경된 코드에서는 \( i \times i \) 연산없이 N과 바로 비교할 수 있다.

 

조건문을 변경하면서, sqrt(N) 함수를 호출하고 있다.

sqrt(N) 함수의 경우, 내부적으로 1번만 연산하고 계속 재활용 된다.

왜냐하면, sqrt(N)의 값은 바뀌지 않기 때문이다. (상수)