myvtm/libtoolkit/intalgo.c

#include "precompile.h"
#include "intalgo.h"

TOOLKIT_API int gcd(int x1, int x2)
{
	int n;
	if (x1 < 0) x1 = -x1;
	if (x2 < 0) x2 = -x2;
	if (x1 > x2) {
		n = x1;
		x1 = x2;
		x2 = n;
	}
	while (x2) {
		n = x1 % x2;
		x1 = x2;
		x2 = n;
	}
	return x1;
}

TOOLKIT_API int  cprime(int n)
{
	int p , q , r;

	if(n <= 2) return 2;
	if(n <= 3) return 3;
	if(! (n & 1)) n++;
	while (1) {
		p = 3;
		q = n - 3;
		r = 9;
		while(q % p) {
			p++;
			r += (p << 2);
			q -= 2;
			if(r > n) return n;
			p++;
		}
		n += 2;
	}
}

TOOLKIT_API int isqrt(unsigned N)
{
	unsigned l2, u, v, u2, n;
	if(2 > N) {
		return N;
	}
	u = N;
	l2 = 0;
	/* 1/2 * log_2 N = highest bit in the result */
	while((u >>= 2)) {
		l2++;
	}
	u = 1L << l2;
	v = u;
	u2 = u << l2;
	while(l2--) {
		v >>= 1;
		n = (u + u + v) << l2;
		n += u2;
		if(n <= N) {
			u += v;
			u2 = n;
		}
	}
	return u;
}