/*!\file:  CyclicalFactorization.cpp
 * \brief given num_procs, finds the integers nprows and npcols so that nprows*npcols=num_procs and nprows-npcols is the smallest possible
*/
#include <math.h>

#include "../../../shared/shared.h"

int SmallestPrimeFactor(int* output,int input);

int CyclicalFactorization(int* pnprows,int* pnpcols,int num_procs){

	int nprows,npcols;
	int last_diff;
	int i;
	int diff;

	nprows=1; npcols=num_procs; last_diff=npcols-nprows;
	for (i=1;i<=num_procs;i++){
		if ((num_procs % i)==0){
			diff=(int)fabs((double)(i-(num_procs/i)));
			if (diff<last_diff){
				nprows=i;npcols=num_procs/i;
				last_diff=(int)fabs((double)(nprows-npcols));
			}
		}
	}
	/*Order nprows > npcols*/
	if (nprows<npcols){
		int temp=nprows;
		nprows=npcols;
		npcols=temp;
	}

	*pnprows=nprows;
	*pnpcols=npcols;

}

int PrimeDecomp(int** pdecomp,int* pdecomp_size,int input){

	int prime_factor;
	int i;

	int* decomp=xNew<int>(input);
	*decomp=input;
	for (i=0;i<input;i++){
		SmallestPrimeFactor(&prime_factor,*(decomp+i));
		if (prime_factor==*(decomp+i)){
			*pdecomp_size=i;
			break;
		}
		else{
			*(decomp+i+1)=*(decomp+i)/prime_factor;
			*(decomp+i)=prime_factor;
		}
	}
	*pdecomp=decomp;
}

/*SmallestPrimeFactor: 
	seeks the smallest prime factor in the prime factor decomposition 
	of integer input
*/
int SmallestPrimeFactor(int* output,int input){

	int found=0;
	int i;

	for (i=2;i<input;i++){
		if ((input %i)==0){
			found=i;
			break;
		}
	}
	if(found){
		*output=found;
	}
	else{
		*output=input;
	}
}
