//Doxaras Ioannis University of Athens
//Division of Nuclear Physics and Elementary Particles

/*Algorithm for simulating Shor's procedure for factoring quantum
mechanicly a large composite number N into primes.
First we choose a random number [1...N-1] and using Eucleid's Algorithm
we check if the number we generated has no common devisors with N.
The distribution of co-prime number lower than N is determined [Hardy] 
\phi(n)=m\prod_{p|m}(1-\frac{1}{p}) were m=\prodp^{c}*/

void prime(Int_t numb)
{

	gROOT->Reset();

	Int_t rand = 7;
	Int_t remainder;
	Int_t quotient;
	Int_t seed = 1;
	
	gBenchmark->Start("Prime");

	//do
	//{
		gRandom = new TRandom3(seed);
		rand = ceil(numb*gRandom->Rndm());
		
	//Eucleid's Algorithm
 
	//	remainder = &rand; //initialize
	//	quotient = &numb;

//		while (remainder != 1) 
//		{
//			quotient = quotient / remainder;
//			remainder = fmod( quotient, remainder); 
//		}
//	    seed += 1;
//	}while(quotient!= 0 || seed > 20);

    cout << "The random number generated is: " << rand << endl;
	
	//Create the Histograms
	Int_t nbins = 128;
	Int_t min = 0;
	Int_t max = 127;
	Double_t c2, c3;
	TH1F * order = new TH1F("order","ORDER",nbins,min,max);
	TH1F * modulo = new TH1F("modulo","modulo",nbins,min,max);

	
	for (Int_t k = 0; k < 128; k++ )
	{ 
		c2 = pow( rand , k );
		c3 = fmod(c2, numb);
		cout << "For: " << k << " show: " << c2 << "  and  " << c3 << endl;
		order->Fill(k , k);
		modulo->Fill(k, c3);
	}


	//Draw Options

	TCanvas *c1 = new TCanvas("Order","",200,10,700,780);
	c1->SetFillColor(0);
	c1->Divide(1,2);
    order->GetXaxis()->SetTitle("Potential orders of probabilistic algorithm");
    order->GetXaxis()->SetTitleFont(32);
    order->GetXaxis()->SetLabelFont(32);
    order->GetXaxis()->SetLabelSize(0.03);
         
	c1->cd(1);
    order->Draw(); // plot the spectrum
	c1->cd(2);
	modulo->Draw(); // plot the spectrum
    c1->Update(); // update the canvas

	gBenchmark->Show("Prime");

}