Codility: Count Factors Solution
Task
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].
Solution
This is a trivial question. Simply iterate over possible factors, testing each in turn.
All unique pairs of factors must have one value less than or equal to the square root. The number of factors is incremented by 2 for each factor found, because N/factor is also a factor.
This does not apply to the square root itself, if it is an integer.
The code could be faster if a sieve of Eratosthenes was used.
#include <math.h>
int solution(int N) {
int res = 0;
float sqr = sqrt(N);
for (int i = 1; i <= sqr; i++) {
if (N % i == 0) {
res += 2;
// don’t double count sq root
if (i == sqr)
res -= 1;
}
}
return res;
};Test Function
This code tests the solution
int main() {
assert(solution(3) == 2);
assert(solution(1) == 1);
assert(solution(24) == 8);
assert(solution(2147483647) == 2);
assert(solution(2147483646) == 192);
assert(solution(2) == 2);
assert(solution(4) == 3);
assert(solution(5) == 2);
assert(solution(6) == 4);
assert(solution(16) == 5);
assert(solution(36) == 9);
assert(solution(41) == 2);
assert(solution(42) == 8);
assert(solution(1000000000) == 100);
assert(solution(2147395600) == 135);
}Results
Codility Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(√N) |