Given a positive integer n
, your task is to find all of its divisors.
A divisor of a number n
is any number that divides n
completely (i.e., leaves no remainder).
Return the list of all such numbers in ascending order.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int cmpfunc(const void* a, const void* b) {
int x = *(const int*)a;
int y = *(const int*)b;
return (x - y);
}
int main() {
int n = 36; // Example number
int maxDivisors = 1000;
int divisors[maxDivisors];
int count = 0;
int sqrtN = (int)sqrt(n);
for (int i = 1; i <= sqrtN; i++) {
if (n % i == 0) {
divisors[count++] = i;
if (i != n / i) {
divisors[count++] = n / i;
}
}
}
qsort(divisors, count, sizeof(int), cmpfunc);
printf("Divisors of %d: ", n);
for (int i = 0; i < count; i++) {
printf("%d ", divisors[i]);
}
printf("\n");
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(√n) | In the best case, all divisors come in pairs (i, n/i), and the loop only runs up to √n. This ensures only √n iterations, even if n is a perfect square. |
Average Case | O(√n) | On average, the loop runs from 1 to √n and checks each number to see if it divides n. Each valid divisor may add up to two numbers to the list (i and n/i), but the loop count is still √n. |
Worst Case | O(√n) | Even if n is a large prime or perfect square, the number of iterations is limited to √n, making this approach efficient for all input sizes. |
Comments
Loading comments...