//lab 4
using System;
using System.Diagnostics;
using System.Collections.Generic;

class MainClass
{
    //z1
    static Int32[] NWD_odejmowanie(int a, int b)
    {
        int counter = 0;
        while (a != b)
        {
            if (a > b)
                a -= b;

            else
                b -= a;

            counter++;
        }
        return new Int32[2] { a, counter };
    }
    //z1
    static Int32 NWD_modulo(int a, int b)
    {
        int counter = 0;
        while (b != 0)
        {
            int r = a % b;
            a = b;
            b = r;
            counter++;
        }
        return a;
    }
    //NWD przez modulo jest o wiele szybsze
    //z5
    /// <summary>
    /// Wyznacza n-ty element ciągu Fibonacciego
    /// </summary>
    /// <param name="n">nty element</param>
    /// <returns>zwraca wartosc n-tego elementu</returns>
    static int Fib(int n)
    {
        if (n == 0)
        {
            return 0;
        }
        else if (n == 1)
        {
            return 1;
        }
        else
        {
            int fa = 0;
            int fb = 1;
            int fi = 0;
            for (int i = 2; i <= n; i++)
            {
                fi = fa + fb;
                fa = fb;
                fb = fi;
            }
            return fi;
        }
    }
    //z6
    /// <summary>
    /// zwraca zbior liczb Fib do pewnej liczby
    /// </summary>
    /// <param name="n">koncowy przedzial</param>
    /// <returns>tablica z liczbami Fib</returns>
    static int [] zbiorFib(int n)
    {
        int[] fib = new int[n + 1];
        int sum = 0;
        for (int i = 0; i < n + 1; i++)
        {
            fib[i] = Fib(i);
        }
        return fib;
    }

    static int sumFib(int n)
    {
        int[] fib = new int[n + 1];
        int sum = 0;
        for (int i = 0; i < n + 1; i++)
        {
            fib[i] = Fib(i);
            sum += fib[i];
            Console.WriteLine(i + " " + sum);
        }
        return sum;
    }
    //z7
    /// <summary>
    /// Metoda liczaca czy liczba jest pierwsza
    /// </summary>
    /// <param name="n"> jaka liczba ma byc sprawdzona</param>
    /// <returns>jesli jest pierwsza zwaca true inaczej false</returns>
    static bool czyPierwsza(int n)
    {
        if (n <= 1)
            return false;
        for(int i=2;i<n;i++)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
    //z8
    /// <summary>
    /// zwraca liczby pierwsze w przedziale
    /// </summary>
    /// <param name="z">od</param>
    /// <param name="x">do</param>
    /// <returns> lista liczb pierwszych</returns>
    static List<int> przedzialPierwszych(int z,int x)
    {
        List<int> przedzial = new List<int>();
        while (z < x)
        {
            if (czyPierwsza(z) == true)
                przedzial.Add(z);

            z++;
        }
        return przedzial;
    }
    static List<int> przedzialPierwszych8(int a,int b)
    {
        if (b == 1)
        {
            return przedzialPierwszych(1, a);
        }
        else
        {
            return przedzialPierwszych(a, b);
        }
    }
    //z10
    static bool wpadkaPierwsza(int n) {
        bool result = false;
        for (int i = 2; i < n; i++) {
            if (n % i != 0) {
                result = true;
                break;
            }
            continue;
        }
        return result;
    }
    /// <summary>
    /// nwm czy dziala tak jak ma to dzialac.
    /// </summary>
    /// <param name="a">od</param>
    /// <param name="b">do </param>
    /// <returns>liczby pierwsze z przedzialu</returns>
    static List<int> przedzialPierwszychWpadka(int a, int b)
    {
        List<int> przedzial = new List<int>();
        for (int i = 2; i < b; i++) {
            if (wpadkaPierwsza(i) == true) {
                przedzial.Add(i);
            }
        }
        return przedzial;
    }
    static List<int> pierwiastekPierwszej(int a, int b) {
        List<int> wynik = new List<int>();
        while (a < b) {
            if (SqrtN(a) == true) {
                wynik.Add(a);
            }
            a++;
        }
        return wynik;
    }
    /// <summary>
    /// piewiastek pierwszej
    /// </summary>
    /// <param name="x"></param>
    /// <returns></returns>
    public static bool SqrtN(int x)
    {
        double d = Math.Ceiling(Math.Sqrt(x));
        for (int i = 2; i < d; i++)
        {
            if (x % i == 1)
            {
                return false;
            }
        }
        return true;
    }
    /// <summary>
    /// sito Eratostenesa
    /// </summary>
    /// <param name="a">od</param>
    /// <param name="b">do</param>
    /// <returns></returns>
    public static void Main(string[] args)
    {
        Stopwatch watch;
        watch = new Stopwatch();
        watch.Restart();
        Console.WriteLine("NWD odejmowanie: " + NWD_odejmowanie(122, 41)[0]);
        watch.Stop();
        Console.WriteLine("Czas odejmowania {0}", watch.Elapsed);
        watch.Restart();
        Console.WriteLine("NWD modulo: " + NWD_modulo(122, 41));
        watch.Stop();
        Console.WriteLine("Czas modulo: " + watch.Elapsed);
        Console.WriteLine("Fibonaci 4 liczba:" + Fib(4));
        Console.WriteLine("suma 4 liczb fib:" + sumFib(4));

        Console.WriteLine("czy pierwsza: "+ czyPierwsza(7));
        List<int> arr = przedzialPierwszych(1, 9);
        foreach(int a in arr)
        {
            Console.Write(a + ",");
        }
        Console.Write( "\n");

        List<int> arr8 = przedzialPierwszych8(12, 1);
        foreach(int a8 in arr8)
        {
            Console.Write(a8 + ",");
        }
        Console.WriteLine("Liczba liczb pierwszych w przedziale:" + arr8.Count);
        Console.WriteLine(SqrtN(4));
        List<int> pierwszaWpadkaList = przedzialPierwszychWpadka(1,8);

        Console.WriteLine("Pierwsza wpadka: \n");
        foreach (int item in pierwszaWpadkaList){
            Console.WriteLine(item);
        }
        /*
        List<int> pierwiastki = pierwiastekPierwszej(1, 89);
        foreach (int p in pierwiastki) {
            Console.Write(p + ",");
        }
         * */
        Console.ReadKey();
    }
}