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!