MMH

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

namespace MMH
{
    class Prime
    {
        private int[] _primes;
        private int _total = 0;

        public Prime()
        {
            _primes = new int[168];
            init();
        }
        private bool temp_init(int n)
        {
            if (n < 2)
                return false;
            if (n == 2)
                return true;

            int temp = (int)Math.Sqrt(n);

            int i = 0;
            for (; i < _total && _primes[i] <= temp; i += 1)
            {
                if (n % _primes[i] == 0)
                    return false;
            }

            return true;
        }
        private void init()
        {
            _primes[_total++] = 2;
            for (int i = 3; i < 1000; i += 2)
            {
                if (temp_init(i))
                {
                    _primes[_total++] = i;
                }
            }
        }
        public bool is_prime(int n)
        {
            if (n < 2)
                return false;

            if (n < _primes[_total - 1])
            {
                int first = 0, last = _total -1;
                while (first <= last)
                {
                    int mid = (first + last) / 2;
                    if (_primes[mid] == n)
                        return true;
                    else
                    {
                        if (_primes[mid] < n)
                        {
                            first = mid + 1;
                        }
                        else
                        {
                            last = mid - 1;
                        }
                    }
                }
                return false;
            }
            else
            {
                return temp_init(n);
            }
        }

        public int rand_prime(int min = 2, int max = 10000)
        {
            Random rand = new Random();
            while (true)
            {
                int n = rand.Next(min, max);
                if (is_prime(n))
                    return n;
            }
            return -1;
        }
        public int max_prime(int max = 10000)
        {
            for (int i = max; i >= 2; i--)
            {
                if (is_prime(i))
                    return i;
            }

            return -1;
        }
    }

    class GCD
    {
        public static int FindGCD(int a, int b)
        {
            while (a != b)
            {
                if (a > b) a = a - b;
                else b = b - a;
            }
            return a;
        }
    }

    class Modulo
    {
        // x^e % n
        public static int MOD (int x, int e, int n)
        {
            if (e == 1)
                return x % n;

            return ((x % n) * MOD(x, e - 1, n)) % n;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Prime p = new Prime();
            // random 1 so nguyen to trong khoang 2 den 10000
            Console.WriteLine("So nguyen to ngau nhien n < 10000: n = " + p.rand_prime(2, 10000));

            // tim so nguyen to lon nhat nho hon 5000
            Console.WriteLine("So nguyen to lon nhat n < 5000: n = " + p.max_prime(5000));

            // tim so nguyen to lon nhat nho hon 10000
            Console.WriteLine("So nguyen to lon nhat n < 10000: n = " + p.max_prime(10000));

            // kiem tra so nguyen bat ky nho hon 1000000 co phai so nguyen to khong
            Random rand = new Random();
            int n = rand.Next(0, 1000000);
            if (p.is_prime(n))
                Console.WriteLine(n + " la so nguyen to");
            else
                Console.WriteLine(n + " khong phai la so nguyen to");

            // xac dinh uoc chung lon nhat cua 2 so duoi 10000
            Console.WriteLine("UCLN(9892, 12) = " + GCD.FindGCD(9892, 12));

            // xac dinh mod cua x^e mod n
            Console.WriteLine("(123 ^ 892) % 14 = " + Modulo.MOD(123, 892, 14));
        }
    }
}