Euler Totient: Optimization

Question

int main(void)
{
  int n, div, a, b;
  double phi;
  printf("Enter n:\n");
  if (scanf("%d", &n) < 1 || n <= 0)
  {
    printf("Wrong input.\n");
    return 1;
  }

  a = n;
  div = 2;
  phi = n;

  while (n != 1)
  {
    if (n % div != 0)
      div++;
    else
    {
      n = n / div;
      if (b != div)
      {
        b = div;
        phi = phi * (1.0 - 1.0 / div);
      }
    }
  }

  printf("phi(%d) = %.f\n", a, phi);

  return 0;
}

This is my code for Eulers Totient I made as a school assignment. The program seems to run fine but is still slow. How can I make it faster please?

Did you profile the code? Do you know where the bottleneck is? — Floris, Nov 01 '13 at 12:37
Should you initialize `b` before you enter the loop?? It is accessed in the `if(b!=div)` line before being assigned a value. Probably not the reason for being slow... Can you give us an idea of the expected vs actual speed? Did you try compiling with `-O3` flag? — Floris, Nov 01 '13 at 12:41
I felt no need to initialize it sooner because the first cycle of that loop I need it to not be equal to div. This is my method of finding unique prime numbers (e.g. 45 consists of 3, 3, 5 and I need only 3 and 5). How fast - there is a certain test that inputs big numbers and the time limit is 2 seconds. — Sorry, Nov 01 '13 at 12:50
If you don't assign it, how can you be sure it isn't equal to `div`? (The correct answer is: you cannot, unless you initialize it first) — Klas Lindbäck, Nov 01 '13 at 12:52
It doesn't have a value so it cannot be equal to the value div has, right? That's my logic but of course I may be wrong. So for example b=1 should be right? — Sorry, Nov 01 '13 at 12:54
I would still recommend initializing `b` to zero - it would happen at compile time and is good defensive coding (or one day it might be "randomly" equal to `div` in the first loop). What is the "big test number"? What is your current timing? You are dividing by `div` twice; compute the reciprocal once and re-use it. Consider using double throughout - on some platforms that is faster than integer math. — Floris, Nov 01 '13 at 12:56
Variables in C are not like variants in BASIC - just because you didn't explicitly give them a value doesn't mean they have one (namely the contents of the memory location they were given: "whatever stuff the kid left in his locker at the end of the school year is still there until you clean it out and put your own stuff in") — Floris, Nov 01 '13 at 12:58
Make sure to use search: http://stackoverflow.com/q/1024640/149530 — Michael Foukarakis, Nov 01 '13 at 13:35

score 1 · Accepted Answer · answered Nov 01 '13 at 13:00

1

First check for div=2.

After that you only need to check odd numbers, so you can use div += 2. That should cut the time in half.

answered Nov 01 '13 at 13:00

Klas Lindbäck

33,105
5
57
82

score 0 · Answer 2 · answered Nov 01 '13 at 13:37

I'm not sure there's a better algorithm, but we can start from the low hanging fruit: you're testing all numbers up to n to find its divisors. This is redundant, as from the definition of φ(n) we know we only need its prime factors.

Great, one might say, we just turned a linear search into a super-polynomial problem.

Not necessarily.

Take the P6 prime candidate generator:

def P6():
    yield 2
    yield 3
    i = 5
    while True:
        yield i
        if i % 6 == 1:
            i += 2
        i += 2

and let's build a factorization function on top of it:

def factors(n):
    d = {}
    primes = p6()
    for p in primes:
        while n % p == 0:
            n /= p
            d[p] = d.setdefault(p, 0) + 1
        if n == 1:
            return d

Now finding φ(n) is trivial. Try implementing this in C and measure the difference. If you need it to be faster, libraries like GMP can provide much faster factorisation routines.

Euler Totient: Optimization

2 Answers2