[Codility] Lesson10 - Prime and Composite numbers : CountFactors (c++)

Problem

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

int solution(int N);

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..2,147,483,647].

How to solve

- 정보

정수 N!

 

- 구해야 하는것?

N의 약수의 갯수

 

- 예시

24의 약수의 갯수 1, 2, 3, 4, 6, 8, 12, 24!

 

- 풀이

N=24인 경우, 

sqrt(24)의 약수 * 2

 

N=25인 경우, 

sqrt(25)의 약수 * 2 +1

 

즉, 

sqrt(N)의 제곱이 N이 아니면, 

N의 약수의 수 = sqrt(N)의 약수의 수*2

 

sqrt(N)의 제곱이 N이면,

N의 약수의 수 = sqrt(N)의 약수의 수*2+1

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(int N) {
    // write your code in C++14 (g++ 6.2.0)
    int count = 0;
    float sqrtN = sqrt(N);
    
    if(N==1){
        return 1;
    }

    for(int i=1; i<sqrtN; i++){
        if( N%i == 0){
            cout << i << endl;
            count += 2;
        }
    }

    if(pow(sqrtN , 2) == N){
        count++;
    }
    return count;
}

Test Result

 

app.codility.com/demo/results/trainingYFD9NG-QKP/

Test results - Codility