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

1. 속도 개선 아이디어

약수는 쌍으로 존재하는 특징을 이용하면 전체 탐색을 하지 않아도 된다.

 

수학적 이론: 약수와 소수

구현: 약수의 개수 구하기

 

2. 코드 (C++)

int solution(int N) {

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

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

    return cnt;
}

 

3. 결과