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 = 25 *
34* 53 * 72 *111
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!
| 
