Useful Number Theory functions in C

During various projects in school and later in university, I faced the problem of having to 'invent' my own functions to solve some Number Theory problems, because stangely enough, in the internet one can't easily find some consistent place with everything one could need to solve Number Theory problems in a comprehensible form (at least, I couldn't find a place...:-).

So, having suffered a bit myself trying to figure out these useful functions, I would like to contribute them to our E2 community.

DISCLAIMER: These functions are almost simple-minded, i.e. they just follow a simplistic approach and are not intended to be used to crack PGP encrypted documents and such. Except if you are *really* patient :-)
And something more: these functions use some simple math functions such as 'sqrt' which are included in the standard math library of C.

So, in your programs just insert at the beginning:
#include "math.h"
and compile like that:
gcc -lm programname.c

---

Let's begin with a simple and robust function which decides on the primality of an integer number.

int isprime(int x)
{
    int i, s;
 
    if (x < 2) return 0;
    if (x % 2 == 0){
      if (x == 2) return 1;
      else return 0;
    }
    for (i = 3, s = sqrt(x); i <= s; i+=2)
        if (x % i == 0) return 0;
    return 1;
}

This function was made twice as fast thanks to Jongleur!

The function is used like that:
isXprime = isprime(500);
and returns '1' in case of a prime number and '0' in case of a non-prime number.


The next function solves the problem of the factorization of an integer (N > 1).

void factor(int thenumber)
{
  int tmp, prime, exp=0, tmpnum = thenumber;
  printf("%d: ",thenumber);
  prime=2;
  while((!isprime(tmpnum)) && (tmpnum != 1)){
    while((!(tmpnum % prime)) && (tmpnum != 1))
     {
       tmpnum /= prime;
       exp++;
     }

    if (exp) printf("%d^%d ",prime,exp);
    exp=0;
    while(!isprime(++prime));
  }
  if (tmpnum != 1) printf("%d^1",tmpnum);
  return;
}

To find the prime factor analysis of an integer, you just have to insert in your C program the next line:
factor(174636000)
The result will be the following:
174636000: 2^5 3^4 5^3 7^2 11^1
which obviously stands for 174.636.000 = 2⁵ * 3⁴* 5³ * 7² *11¹


The next function is used to find how many divisors a specific integer (N > 1) has.

int divisors(int x)
{
    int num = x, prime = 2, prod = 1, times = 0;
    if (x <= 2) return x;
    do {
	if (x % prime == 0) {
	    x /= prime;
	    ++times;
	}
	else {
	    prod *= ++times;
	    num = x;
	    while (!is_prime(++prime));
	    times = 0;
	}
    } while (!is_prime(num) && num != 1);
    return num == 1 ? prod : prod << 1;
}

As you will notice, the code of this function is exactly the same as the previous function which accomplishes the factorization. The reason can be found at the divisor node, in a little theorem which allows us to find how many divisors a number has if we know its prime factor analysis.
Note that this function returns the number of an integer's divisors including 1 and the number itself.
Example: divisors(10) yields 4 (divisors: 1, 2, 5, 10).

I thoroughly tested the above functions and they do no seem to have any bugs. Feel free to comment on the algorithms, and add functions which you find useful for Number Theory problems.

Special thanks to Vasilis Vasaitis for some optimizations!