Did not find a good dup. Here is a solution with O(sqrt(n)) complexity. It's taken from https://www.geeksforgeeks.org/count-divisors-n-on13/
// function to count the divisors
int countDivisors(int n)
{
int cnt = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
// If divisors are equal,
// count only one
if (n / i == i)
cnt++;
else // Otherwise count both
cnt = cnt + 2;
}
}
return cnt;
}
On the same site, there is one that runs in O(n^(1/3)) that is slightly more complex. It's for C++, but just add #include <stdbool.h> and it should work.
void SieveOfEratosthenes(int n, bool prime[],
bool primesquare[], int a[])
{
// Create a boolean array "prime[0..n]" and initialize all entries as
// true. A value in prime[i] will finally be false if i is Not a prime,
// else true.
for (int i = 2; i <= n; i++)
prime[i] = true;
// Create a boolean array "primesquare[0..n*n+1]" and initialize all
// entries it as false. A value in squareprime[i] will finally be true
// if i is square of prime, else false.
for (int i = 0; i <= (n * n + 1); i++)
primesquare[i] = false;
// 1 is not a prime number (Look it up if you doubt it)
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
int j = 0;
for (int p = 2; p <= n; p++) {
if (prime[p]) {
// Storing primes in an array
a[j] = p;
// Update value in primesquare[p*p], if p is prime.
primesquare[p * p] = true;
j++;
}
}
}
// Function to count divisors
int countDivisors(int n)
{
// If number is 1, then it will have only 1
// as a factor. So, total factors will be 1.
if (n == 1)
return 1;
bool prime[n + 1], primesquare[n * n + 1];
int a[n]; // for storing primes upto n
// Calling SieveOfEratosthenes to store prime factors of n and to store
// square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a);
// ans will contain total number of distinct divisors
int ans = 1;
// Loop for counting factors of n
for (int i = 0;; i++) {
// a[i] is not less than cube root n
if (a[i] * a[i] * a[i] > n)
break;
// Calculating power of a[i] in n.
int cnt = 1; // cnt is power of prime a[i] in n.
while (n % a[i] == 0) // if a[i] is a factor of n
{
n = n / a[i];
cnt = cnt + 1; // incrementing power
}
// Calculating number of divisors. If n = a^p * b^q then total
// divisors of n are (p+1)*(q+1)
ans = ans * cnt;
}
// if a[i] is greater than cube root of n
// First case
if (prime[n])
ans = ans * 2;
// Second case
else if (primesquare[n])
ans = ans * 3;
// Third casse
else if (n != 1)
ans = ans * 4;
return ans; // Total divisors
}
If the above is not enough, you should look into some kind of dynamic programming. Both of the above method is calculating each number from scratch. But if you're going to do it for several numbers, it is quite possible that you can use information from previous numbers. Just to give an idea for how it works, here is an algorithm calculating all primes from 2 to n:
#include <stdbool.h>
#include <stdio.h>
#include <math.h>
// After running this function, prime[n] will be true iff n is a prime
void createPrimeArray(bool *prime, size_t size)
{
prime[0] = prime[1] = false;
for(size_t i=2; i<size; i++)
prime[i] = true;
for(size_t i=2; i<sqrt(size); i++) {
size_t j=i;
while(!prime[j])
j++;
for(size_t k=2*j; k<size; k+=j)
prime[k] = false;
}
}
int main(void)
{
bool prime[200];
createPrimeArray(prime, 200);
for(int i=0; i<200; i++) {
if(prime[i])
printf("%d ", i);
}
}
The above can possibly be optimized further. It's purpose is to show how you can reuse information. After the first run in the second for loop in createPrimeArray we have marked all numbers that are dividable by 2 as non-primes, and thus we don't have to care about those anymore.
