#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

// A function to print all prime factors of a given number n
// Code based on http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
//
int primeFactors (long n, long list[])
{
	volatile int 	c = 0;  // counter for list
	long 			r;		// root n

	// Print the number of 2s that divide n
	while (n % 2 == 0)
	{
		list[c++]=2;
		n = n / 2;
	}
	r=sqrt(n);

	// n must be odd at this point.  So we can skip one element (Note i = i +2)
	for (long i = 3; i <= r ; i = i + 2)
	{
		// While i divides n, print i and divide n
		while (n % i == 0)
		{
			list[c++]=i;
			n = n / i;
			r=sqrt(n);
		}
	}

	// This condition is to handle the case whien n is a prime number
	// greater than 2
	if (n > 2)
	{
		list[c++]=n;
	}
	return(c);
}
//RandomX updated 5/30 at 5:40pm
//Note: not uniformly random, but frankly my dear, I don't...
long randomX(long min, long max)
{
    long value=(long)rand()<<32 | rand();
    return value%(max-min)+min;
}

long gcd(long a, long b)
{
	long 	listi[64], listj[64];
	int 	i=0,j=0;

	int 	maxi, maxj;
	long 	gcd=1;
	

	maxi=primeFactors(a,listi);
	maxj=primeFactors(b,listj);

	while(i<maxi && j<maxj)
	{
		if(listi[i]==listj[j])
		{
			gcd=gcd*listi[i];
			i++; 
			j++;
		}
		else if (listi[i]>listj[j])
			j++;
		else
			i++;
	}
	return(gcd);
}

int main()
{
	int c=0;
	long bob;
	if(sizeof(long)<8)
	{
		cerr << "sizeof long=" << sizeof(long) << " but should be 8.  Need a 64 bit machine or some compiler flags" << endl;
		exit(1);
	}
	//srand(time(0)); // Randomize rand

	
	clock_t tick=clock();

	while(c<10000000)
	{
		//gcd(randomX(10000000,99999999),randomX(10000000,99999999));
		gcd(randomX(100,999),randomX(100,999));
		c++;
	}
    clock_t toc=clock();
	cout << "runtime is " << (double)(toc-tick)/CLOCKS_PER_SEC 
		 << "seconds"<< endl;
	return 0;
    
}