trees in a wood.cpp

trees in the woods 俗语： "你不能看到木为树"

// FEFE.cpp : Defines the entry point for the console application.
//

// TreesOfWood.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "math.h"
#define MAXX 2000
#define MAXY 2000000

static unsigned int index = 5;
static unsigned int nPrimes[10000000] = {2, 3, 5, 7, 11, 0};
void PrimesInNumber(unsigned int n) ;
unsigned int fni(unsigned int n);
unsigned int TotalTreesOfWood(unsigned int a, unsigned int b);
unsigned int gcd1(unsigned int n1, unsigned int n2);
unsigned int gcd2(unsigned int n1, unsigned int n2);
unsigned int gcd3(unsigned int n1, unsigned int n2);
unsigned int SeenTreesOfWood(unsigned int a, unsigned int b);

int  main(int argc, char* argv[])
{
	unsigned int fnif = 0, totTrees = 0;
	double result = 0.0;
	unsigned int nx = 0, ny = 0, nmax = 0;
	unsigned int seenTrees = 0;

	while(1) {
		scanf("%u %u", &nx, &ny);
		printf("You had input --> x = [%u]  y = [%u]\n", nx, ny);
		if(nx == 0 && ny == 0) {
			printf("Pls input non-zero numbers....\n");
			continue;
		}
		break;
	}

	if(nx > MAXX) nx = MAXX;
	if(ny > MAXY) ny = MAXY;

	nmax = nx + ny;
	PrimesInNumber(nmax);

    seenTrees = SeenTreesOfWood(nx, ny);

	seenTrees = seenTrees * 4;
	totTrees = TotalTreesOfWood(nx, ny);

    result = (double)seenTrees / (double)totTrees;

	printf("result = %8.8f\n", result);

	return 0;
}


// fni(n) = n xx (1 - 1 / p);  p belong to prime and p|n; 
unsigned int fni(unsigned int n)
{
	unsigned int fni = 1; 

    if(n == 0) return 0;
	if(n == 1 || n == 2) return 1;
	if(n == 3) return 2;
	fni = n;
	for(int ind = 0; nPrimes[ind] <= n; ind++) {
		if( !(n % nPrimes[ind]) )	{
			fni = fni - fni / nPrimes[ind];
		}
	}

    return fni;
}


unsigned int TotalTreesOfWood(unsigned int a, unsigned int b)
{
	if(!a || !b) return 0;

	return (2 * a + 1) * ( 2 * b + 1) - 1;
}

unsigned int SeenTreesOfWood(unsigned int a, unsigned int b)
{
	unsigned int nmax = a + b;
	unsigned int tot = 0;

	if(a == 0 || b == 0) return 1;

	for(int i = 1; i < a + 1; i++) {
		tot += fni(i);
	}

	for( i = a + 1; i < nmax + 1; i++) {
		for(int j = 1; j < b + 1; j++) {
			if((i - j) < a + 1) {
				if(gcd3(i, j) == 1) tot += 1;
			}
		}
	}

	return tot;
}

void PrimesInNumber(unsigned int n) 
{
   unsigned int m = 0;
   if(n == 0) return;
   if((nPrimes[index - 1] * nPrimes[index - 1] + 1) < n) {
	   m = sqrt(n + 0.00001);
	   PrimesInNumber(m);
	   int ind = index;
	   int i = 0;
	   for(i = nPrimes[index - 1] + 1; i <= n; i++) {
		   if(!(i & 1))  continue;
		   else {
			   int j = 0;
			   for(j = 1; j < ind; j++) {
				   if(!(i % nPrimes[j])) break;
			   }
			   if(j == ind) nPrimes[index++] = i;
		   }
	   }
   }
   else {
	   int ind = index;
	   int i = 0;
	   for(i = nPrimes[index - 1] + 1; i <= n; i++) {
		   if(!(i & 1))  continue;
		   else {
			   int j = 0;
			   for(j = 1; j < ind; j++) {
				   if(!(i % nPrimes[j])) break;
			   }
			   if(j == ind) nPrimes[index++] = i;
		   }
	   }

   }

   return;
}

unsigned int gcd1(unsigned int n1, unsigned int n2)
{
	unsigned int nb, ns, result;
	nb = n1; ns = n2;
	if(nb < ns) {int tt; tt = nb; nb = ns; ns = tt;}

	if(! ns) return nb;

	result = gcd1(nb - ns, ns);

	return result;
}

unsigned int gcd2(unsigned int n1, unsigned int n2)
{
	unsigned int yu ;
	if(!n2) return n1;
	yu = n1 % n2;
	return gcd2(n2, yu);
}

unsigned int gcd3(unsigned int n1, unsigned int n2)
{
	unsigned int yu;
    yu = n2;

	while(yu) {
		yu = n1 % n2;
		n1 = n2;
		n2 = yu;
	}

	return n1;
}