1
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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);
} 
\$\endgroup\$
  • \$\begingroup\$ no, printing doesn't matter, I concentrate on the code and logic itself. \$\endgroup\$ – A.M Jun 3 '18 at 10:00
  • 2
    \$\begingroup\$ The printing does matter for the execution speed of your entire program. You get a result of 103119 milliseconds compared to 400 miliseconds by printing. Hence, by not printing, your program will run faster. Though not the actual logic of it. I will edit my post to include my code implementation. \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 12:27
1
\$\begingroup\$

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--;
}
\$\endgroup\$
  • \$\begingroup\$ I tried this and it took approximately 109543 milliseconds. it seems algorithm I wrote is faster or at least the same... \$\endgroup\$ – A.M Jun 2 '18 at 15:03
  • \$\begingroup\$ @A.M you can also try replacing j%2 with j&1 and you can try printing j in hex format so the Console.WriteLine doesn't have to calculate the decimal representation every time (of course the last one doesn't make sense if you really need the decimal representation). \$\endgroup\$ – Aemyl Jun 2 '18 at 16:18
  • \$\begingroup\$ Look at versions of the sieve of Eratosthenes for ways to optimise Aemyl's suggested approach. en.wikipedia.org/wiki/Sieve_of_Eratosthenes Note that Aemyl's suggestion is not actually a sieve: it is testing each candidate number in isolation. What you'd want would be something that loops through a boolean array, marking with false every ith element for i in {2, 3, 5, 13}. Then loop through and return the trues. This promises a considerable speed up, largely by using addition extensively in place of the mod and multiply operations. The downside is memory usage. \$\endgroup\$ – Josiah Jun 2 '18 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.