Euler Problem 73:

How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Solution:

Rješenje problema svodi se na implementaciju metode za najveći zajednički djelilac, te dupla petlja koja prolazi sve integer projeve od 1-12000, s tim da je n<d.

Obzirom da je problem dosta jednostavan kao i brute force algoritam rješava problem za manje od minute, na stranici je dato efikasno objašnjenje zadatka i algortima, koji se bazira na Farey Sequances (Farray-ev niz). Moja Brute – Force implementacija:

static void Main(string[] args)
{
    long counter=0;
    double pol = 0.5;
    double trec = 1.0 / 3.0;
    for (int n = 1; n < 12000; n++)
    {
        for (int d = n + 1; d <= 12000; d++)
        {
            if (HCF(n, d) == 1)
            {
                double frac=((double)n)/((double)d);
                if (frac > trec && frac < pol)
                    counter++;

            }
        }
    }
    Console.WriteLine("Solution PE73={0}", counter);
    Console.WriteLine("Press any key to continue...");
    Console.Read();
}
static long HCF(long n, long d)
{
    while (d != 0)
    {
        long temp = n % d;
        n = d;
        d = temp;
    }
    return n;
}