Find coprime numbers less than n

Question

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

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

while (j > 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.

Answer 1

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 > 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<int> lst = new List<int>();

    while (j > 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 > 1)
    {
        if (GCD(n, j) == 1)
            counter++;

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

Answer 2

To your GCD function: it can be simplified to

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

To your mainloop: If you know the value of n at compile time, you can factorize it and take advantage of the fact that only numbers without any of the prime factors of n are coprime. For n = 15600000, the prime factorization is 2^7 * 3 * 5^5 * 13, so the best thing I can come up with is a specialized version of your GCD usage:

while (j > 1)
{
    // if j is divisible by any of these numbers, it is not coprime to n
    // and the result of this calculation will be 0
    if ((j%2) * (j%3) * (j%5) * j(%13) != 0)
        Console.WriteLine(j);
    j--;
}