4neurons logo


CNumber PF(const CNumber& n)
{
	CNumber p,q,diff,sum,n4,sqrt,i;

	n4=4*n;
	for(i=SQRT(n4)+1;a<=n;++i){
		diff=i*i-n4;
		sqrt=SQRT(diff);
		if(diff==sqrt*sqrt){ //sqrt(diff) belongs to N (this is our suspected p-q)
			sum=diff+n4;
			diff=sqrt;
			sqrt=SQRT(sum);
			if(sum==sqrt*sqrt){ //sqrt(sum) belongs to N (suspected p+q)
				sum=sqrt; //now we got two equations: "p-q = diff" and "p+q = sum"
				q=(sum+diff)/2;
				p=q-diff;
				if(p*q==n) 
					return p;
			}
		}
	}	
	return 1;
}