#include <stdio.h>
#include <iostream.h>

class list{
public:
 int value;
 list* pnext;
 ~list(){
 if (pnext!=0){delete pnext;}
 }
};

class chain{
public:
list* pfirst;
list* plast;
int size;
chain(){
size=0;
pfirst=0;
}
~chain(){
if (pfirst!=0){delete pfirst;}
}
void addnew(int	val){
 size++;
 list* current=new list;
 if (pfirst==0){pfirst=current;}else{plast->pnext=current;}
 plast=current;
 current->pnext=0;
 current->value=val;
}
int grecord(int	val){
int rnum=0;
for (list* current=this->pfirst;current;current=current->pnext){
rnum++;
if (rnum==val){return current->value;}
}
return -1;
}
void output(){
cout <<	"\n";
for (list* current=this->pfirst;current;current=current->pnext){
cout <<	current->value << ",";
}
}
};

class pfargstruct{
public:
pfargstruct(int ofb,chain* targetb){
cpf=0; npf=0;
of=ofb; target=targetb;
}
void found(int cval){
of/=cval;
if (cval==*cpf){
(*npf)++;
}else{
target->addnew(1); npf=&(target->plast->value);
target->addnew(cval); cpf=&(target->plast->value);
}
}
chain* target;
int of;
int* cpf;
int* npf;
};

chain* primes=new chain;
chain* primefs=new chain;
int cnum=1;

int abs(int n){
if (n<0){n=-n;}
return n;
}

void expandfarray(int upto){
int lpf=0;
int test=0;
for (int i=cnum+1;i<=upto;i++){
lpf=i;
for (list* current=primes->pfirst;current;current=current->pnext){
test=current->value;
if ((test*test)>i){break;}
if ((i%test)==0){lpf=test; break;}
}
primefs->addnew(lpf);
if (lpf==i){
primes->addnew(i);
}
}
cnum=upto;
}

void listpfs(pfargstruct* a,pfargstruct* b,int level,list* current){
int cval=current->value;
if ((level<(a->of))|(level<(b->of))){
listpfs(a,b,level+1,current->pnext);
}
if (level==(a->of)){
a->found(cval);
}
if (level==(b->of)){
b->found(cval);
}
}

void listpfs(chain* targeta,int ofa,chain* targetb,int ofb){
pfargstruct* a=new pfargstruct(ofa,targeta);
pfargstruct* b=new pfargstruct(ofb,targetb);
listpfs(a,b,2,primefs->pfirst);
}

void listfs(list* current,chain* flist,int tsofar){
if (current){
int npf=current->value;  current=current->pnext;
int cpf=current->value;  current=current->pnext;
for (int i=0;i<=npf;i++){
listfs(current,flist,tsofar); tsofar*=cpf;
}
}else{
flist->addnew(tsofar);
}
}

void brackets(int x,int y){
cout << "(";
if (x==-1){cout << "-";}else{
if (x!=1) {cout <<  x;}}
cout << "x";
if (y>0){cout << "+";}
cout << y << ")";
}

void check(int a,int inva,int b,int c,int invc){
int bcheck=(a*invc)+(c*inva);
if (b==bcheck){
cout << "\n";
brackets(a,c);
brackets(inva,invc);
}
}

void factorise(int a,int b,int c,chain* fA,chain* fC){
cout << "\nWorking Quadratics:";
for (list* pc=fC->pfirst;pc;pc=pc->pnext){
int ic=pc->value;
for (list* pa=fA->pfirst;pa;pa=pa->pnext){
int ia=pa->value;
if ((ia*ia)<(fA->plast->value)) continue;
check(ia,a/ia,b,-ic,-c/ic);
check(ia,a/ia,b,ic,c/ic);
}
}
}

int main(int nargs,char* pszargs){
cout <<	"Quadratic Factoriser v2.0\n^^^^^^^^^ ^^^^^^^^^^ ^^^^";
int a=0;
int b=0;
int c=0;
char goagain;
for (;;){
chain* pfA=new chain;
chain* pfC=new chain;
chain* fA=new chain;
chain* fC=new chain;
for (;;){
cout <<	"\ninput A:"; cin >> a;
cout <<	"input B:"; cin	>> b;
cout <<	"input C:"; cin	>> c;
if ((a!=0)&(c!=0)){break;}
cout <<	"\nNeither A or C can equal 0\n";
}
if (cnum<abs(a)) expandfarray(abs(a));
if (cnum<abs(c)) expandfarray(abs(c));
listpfs(pfA,abs(a),pfC,abs(c));
listfs(pfA->pfirst,fA,1);
cout << "\nFactors of A:";
fA->output();
listfs(pfC->pfirst,fC,1);
cout << "\nFactors of C:";
fC->output();
factorise(a,b,c,fA,fC);
delete fA; delete fC;
cout <<	"\nGo again y/n?\n";
cin >> goagain;
delete pfA; delete pfC;
if (goagain == 'n'){break;}
}
delete primes; delete primefs;
return 0;
}