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**^{5} *******
3**^{4}******* 5**^{3} *** ****7**^{2} *11^{1}
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!