//10720116鄭宇傑 10720138陳尚宏
#include <iostream>
#include <cstdlib>
#include <list>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
int mission1(int);
unsigned long long mission2(int);
void initial(void);
void printDivisors(unsigned long long);
int mission1_new(int);
unsigned long long fib(int, unsigned long long, unsigned long long);

int fibcount = 0 ;


int rec=0;
struct factorlist
{
    unsigned long long value1,value2,dif;
    struct factorlist *rlink;
    struct factorlist *llink;
};
struct factorlist *head,*tail,*prev,*ptr,*cur;


int main()
{
    int num1;



    while(1)
    {
        int num;
        cout<<"\n"<<"**Fibonacci Series Generator**"<<endl;
        cout<<"* 0.Quit                      *"<<endl;
        cout<<"* 1.Iterative generation      *"<<endl;
        cout<<"* 2.Recursive generation      *"<<endl;
        cout<<"*******************************"<<endl;
        cout <<"Input a command(0,1,2): ";
        cin>>num;
        switch(num)
        {

        case 0:
            exit(1);
            break;
        case 1:
            cout<<"Please input a number:";
            cin>>num1;
            mission1(num1);
            break;
        case 2:
            {


            cout<<"Please input a number:";
            cin>>num1;
            //mission2(num1);
            int outloop = 0;
            for(int i=1; i<=num1; i++)
            {
                outloop++;

                //unsigned long long fnum = mission2(i);
                unsigned long long fnum = fib(i+1,1,0);

                cout<<"["<<i<<"]";
                cout<<fnum;

                unsigned long long firstnum,secnum ;

                int inloop = 0 ;

                for (unsigned long long i1=1; i1<=sqrt(fnum); i1++)
                {
                    if (fnum%i1 == 0)
                    {
                        firstnum = i1;
                        secnum = fnum/i1;
                    }
                    inloop++ ;
                }

                printf(" = ");
                cout<<firstnum;
                printf(" * ");
                cout<<secnum;
                //printf("\n");


                cout<<" (Inner recursion: "<<inloop<<" times)\n";

            }
            cout<<"<Outer recursion: "<<outloop<<" times>\n";
            break;
            }
        default:
            cout<<" Command does not exist."<<endl;
            break;

        }
    }
    return 0;
}




unsigned long long mission2(int num1)
{


    if(num1==0){

        return 1;
    }
    else if(num1==1){

        return 1;
    }
    else
        return mission2(num1-1)+mission2(num1-2);
}

unsigned long long fib(int term, unsigned long long val = 1, unsigned long long prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}



int mission1(int num1)
{
    int t=0,h=0;
    unsigned long long Fib1=1,Fib0=0;
    unsigned long long f[num1];
    for(int i=1; i<=num1; i++)
    {
        unsigned long long Fib;
        Fib=Fib0+Fib1;
        f[t]=Fib;
        Fib0=Fib1;
        Fib1=Fib;
        t++;
    }
    for(int u=0; u<=t-1; u++)
    {
        int n=1,count=0;
        h++;
        unsigned long long b;
        cout<<"["<<u+1<<"]    "<<"["<<f[u]<<"]"<<"\t";
        {
            ptr=(struct factorlist*)malloc(sizeof(struct factorlist));
            ptr->llink=ptr;
            ptr->rlink=ptr;
            head=ptr;
            tail=ptr;
            b=f[u];
            while(n<=f[u]/n)
            {
                if(b%n!=0)
                {
                    n++;
                    continue;
                }
                else
                {
                    count++;
                    ptr=(struct factorlist*)malloc(sizeof(struct factorlist));
                    if(head->rlink==head)
                    {
                        head->rlink=ptr;
                        head->llink=ptr;
                        ptr->rlink=head;
                        ptr->llink=head;
                        ptr->value1=n;
                        ptr->value2=b/n;
                        ptr->dif=((b/n)-n);
                        tail=ptr;
                    }
                    else
                    {
                        ptr=(struct factorlist*)malloc(sizeof(struct factorlist));
                        ptr->rlink=head;
                        ptr->llink=tail;
                        tail->rlink=ptr;
                        head->llink=ptr;
                        ptr->value1=n;
                        ptr->value2=b/n;
                        ptr->dif=((b/n)-n);
                        tail=ptr;
                    }
                    n++;
                }
            }
            cur=head->rlink;
            int a=0,c;
            while(cur!=head)
            {
                a++;
                cur=cur->rlink;
            }
            cur=head->rlink;
            for(int k=1; k<=a-1; k++)
            {
                for(int l=1; l<=a-k; l++)
                {
                    if((cur->dif)<(cur->rlink->dif))
                    {
                        c=cur->dif;
                        cur->dif=cur->rlink->dif;
                        cur->rlink->dif=c;
                    }
                }
            }
            cout<<"= "<<head->llink->value1<<"*"<<head->llink->value2<<"\t"<<"[inner loop= "<<count<<" time]"<<endl;
        }
    }
    cout<<"outer loop= "<<h<<endl;
    return 0;
}