using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp7
{
    class Program
    {
        static public void Main(string[] args)
        {
            Console.ForegroundColor = ConsoleColor.Cyan;//Input 2 integers
            Console.Write("Int 1: ");
            Console.ForegroundColor = ConsoleColor.White;
            int num1 = Convert.ToInt32(Console.ReadLine());
            Console.ForegroundColor = ConsoleColor.Cyan;
            Console.Write("Int 2: ");
            Console.ForegroundColor = ConsoleColor.White;
            int num2 = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine();

            int input = num1;
            List<int> factors1 = Factorise(input);//Finds prime factors of input 1
            input = num2;
            List<int> factors2 = Factorise(input);//Finds prime factors of input 2

            Console.ForegroundColor = ConsoleColor.Cyan; //Prints prime factors of input 1
            Console.Write("Int 1 prime factors: ");
            Console.ForegroundColor = ConsoleColor.White;
            factors1.ForEach(item => Console.Write(item + ", "));
            Console.WriteLine();

            Console.ForegroundColor = ConsoleColor.Cyan;//Prints prime factors of input 2
            Console.Write("Int 2 prime factors: ");
            Console.ForegroundColor = ConsoleColor.White;
            factors2.ForEach(item => Console.Write(item + ", "));
            Console.WriteLine();

            Shared(factors1, factors2, num1, num2);

        }


        static List<int> Factorise(int input)
        {
            List<int> factors = new List<int>();
            int a = 2;
            while (true)
            {
                if (a == input)
                {
                    factors.Add(a);
                    return factors;
                }
                int b = input % a; //b is remainder.
                if (b > 0)
                {
                    //if b is not 0, a is not a factor of input
                    a++;
                }
                else if (b == 0)
                {
                    factors.Add(a);
                    input = (input / a);
                    a = 2;
                }
            }
        }
        static void Shared(List<int> factors1, List<int> factors2, int num1, int num2)
        {
            List<int> shared = new List<int>();
            for (int i = 0; i <= factors1.Count; ++i)
            {
                for (int j = 0; j <= factors2.Count; ++j)
                {
                    if (factors1[i] == factors2[j])
                    {
                        shared.Add(factors1[i]);
                        factors1.Remove(i);
                        factors2.Remove(j);
                        --i;
                        --j;
                        break;
                    }
                }
            }


            Console.ForegroundColor = ConsoleColor.Cyan; //Prints shared factors
            Console.Write("Shared factors: ");
            Console.ForegroundColor = ConsoleColor.White;
            shared.ForEach(item => Console.Write(item + ", "));
            Console.WriteLine();
            Console.WriteLine();

            int hcf = Hcf(shared);
            Console.ForegroundColor = ConsoleColor.Cyan;//Prints HCF
            Console.Write("Highest Common Factor: ");
            Console.ForegroundColor = ConsoleColor.White;
            Console.WriteLine(hcf);
        }
        static int Hcf(List<int> shared)
        {
            int num = 1;
            for (int i=0; i < shared.Count;i++)
            {
                num = shared[i] * num;
            }
            return num;
        }

    }

}