using System;

namespace FacteursPremiers
{
	class MainClass
	{
		
		/***********************************************/
		
		public static bool divise(int diviseur, int n)			
		{
			return n%diviseur == 0;
		}
		
		public static int puiss(int a, int n)
		{
			if (n == 0)
				return 1;
			if (divise(2, n))
				return puiss(a*a, n/2);
			return a*puiss(a, n-1);
		}
			 
		
		public static bool estPremier(int x, int[] premiers, int k)
		{
			for(int i = 0 ; i < k && puiss(premiers[i], 2) <= x ; i++)				
				if (divise(premiers[i], x))
					return false;
			return true;
		}
		
		/***********************************************/
		
		public static int [] trouvePremiers(int n)
		{
			int [] premiers = new int [n];
			premiers[0] = 2;
			int k = 1;
			int x = 3;
			while(k < n)
			{
				if (estPremier(x, premiers, k))
				{
					premiers[k] = x;
					k++;
				}
				x+=2;
			}
			return premiers;
		}
		
		/***********************************************/
		
		public static int[] decompose(int x, int[] premiers)
		{
			int n = premiers.Length;
			int [] decomposition = new int[n];
			int indiceDiviseur=0;
			while(x != 1)
			{
				if (divise(premiers[indiceDiviseur], x))
				{
					decomposition[indiceDiviseur]++;
					x/=premiers[indiceDiviseur];
				}
				else
					indiceDiviseur++;
			}
			return decomposition;
		}	
		
		/***********************************************/
		
		public static int recompose(int[] decomposition, int [] premiers)
		{
			int x = 1;
			int n = decomposition.Length;
			for (int i = 0 ; i < n ; i++)
				x *= puiss(premiers[i], decomposition[i]);
			return x;
		}
		
		/***********************************************/		
		
		public static int min(int a, int b)
		{
			return (a < b) ? a : b;
		}
		
		public static int[] pgcd(int[] T, int[] K)
		{
			int n = T.Length;
			int [] decomposition = new int[n];
			for (int i = 0 ; i < n ; i++)
				decomposition[i] = min(T[i], K[i]);
			return decomposition;
		}
		
		/***********************************************/

		public static int pgcd(int i, int j)
		{	
			int n = 50;
			int [] premiers = trouvePremiers(n);
			int [] tabI = decompose(i, premiers);
			int [] tabJ = decompose(j, premiers);
			int [] pgcdD = pgcd(tabI, tabJ);
			return recompose(pgcdD, premiers);
		}
		
		/***********************************************/

		public static string StringOfTab(int [] t)
		{
			string res = "";
			foreach(int v in t)
				res += v + " ";
			return res;
		}
		
		public static void Main (string[] args)
		{
			int[] premiers = trouvePremiers(50);
			int x = 108108;
			Console.WriteLine("Nombres premiers = " + StringOfTab(premiers));
			int[] decomposition = decompose(x, premiers);
			Console.WriteLine("Decomposition de n = " + StringOfTab(decomposition));
			Console.WriteLine("Recomposition de n = " + recompose(decomposition, premiers));
			int i = 65, j = 110;
			Console.WriteLine("Pgcd (" + i + ", " + j + ") = " + pgcd(i, j));
		}
	}
}