Find coprime numbers less than n I get the coprime numbers less than n with the following algorithm:

int n = 15600000;
int j = n - 1;

while (j &gt; 1)
{
   if (GCD(n, j) == 1)
   Console.WriteLine(j);

   j--;
}


My GCD method, which calculates the greatest common divisor of two numbers, looks like this:

static int GCD(int A, int B)
{
   if (B != 0)
       return GCD(B, A % B);
   else
       return A;
}


This algorithm need approximately 103119 milliseconds on my pc. I am interested in a better (faster and little code) solution to this problem.
Do you really need to print the answers to screen?

Most time consumed by the program is for printing each result to screen, using a simple counter or just saving all element in a list (should you need to work with the values, but not actually see them) saves a massive amount of time. Compare my results below:

With printing each value to console - your original code: 00:03:16.008651

static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int n = 15600000;
            int j = n - 1;

            while (j &gt; 1)
            {
                if (GCD(n, j) == 1)
                    Console.WriteLine(j);

                j--;
            }
            sw.Stop();
            Console.WriteLine("Time elapsed: " + sw.Elapsed);
        } 


Adding value to list and then printing: 00:03:29.6715458 

static void Main(string[] args)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int n = 15600000;
    int j = n - 1;
    List&lt;int&gt; lst = new List&lt;int&gt;();

    while (j &gt; 1)
    {
        if (GCD(n, j) == 1)
            lst.Add(j);

        j--;
    }

    foreach(int ele in lst)
    {
        Console.WriteLine(ele);
    }

    sw.Stop();
    Console.WriteLine("Time elapsed: " + sw.Elapsed);
}


With counter or list (not printing to console): 00:00:04.5160762  

static void Main(string[] args)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int n = 15600000;
    int j = n - 1;
    int counter = 0;

    while (j &gt; 1)
    {
        if (GCD(n, j) == 1)
            counter++;

        j--;
    }
    sw.Stop();
    Console.WriteLine("Time elapsed: " + sw.Elapsed);
}