-1

I want to write a function for finding co-prime numbers for a number N which are less than number M such that M

For that I refered to this link modifying Euler Totient Function

I wrote a following recursive code.

int f(int *factors, int start, int nf, int m) //nf=no. of factors, start=0, m=M
{
    if(start == nf-1) 
        return (m / factors[start]);

    return (m / factors[start]) + f(factors, (start + 1), nf, m) - ((f(factors, (start + 1), nf, m)) / factors[start]);
}

But, I am getting wrong answer.

I want to solve this problem http://www.spoj.pl/problems/HNUMBERS/

My code is giving right answer for given test cases, but failing for some others (as they are showing me wrong answer).

8
  • Can you give an example of wrong answer? Oct 11, 2012 at 17:29
  • I can't understand any of where N appears in your function, what you're problem statement is or what the algorithm you are trying to implement is, or what is going wrong. Please post sample inputs and expected v. actual outputs.
    – djechlin
    Oct 11, 2012 at 17:29
  • Show us your test cases and the results you're getting from each. Oct 11, 2012 at 17:30
  • @djechlin :factors[] array has all prime factors of N. Go through the stackoverflow link which I have given to understand what algorithm I am implementing. I also don't know the failure test cases.Also, suggest different code(if any) to solve this. Oct 11, 2012 at 17:33
  • possible duplicate of modifying Euler Totient Function
    – interjay
    Oct 11, 2012 at 17:39

1 Answer 1

1

Your function f (you should perhaps choose a more descriptive name) seems to be meant to return the count of numbers not exceeding m that are divisible by any of the primes in the array factors, from the index start onwards.

int f(int *factors, int start, int nf, int m) //nf=no. of factors, start=0, m=M
{
    if(start == nf-1) 
        return (m / factors[start]);

    return (m / factors[start]) + f(factors, (start + 1), nf, m)
              - ((f(factors, (start + 1), nf, m)) / factors[start]);
}

Obviously, with only one prime p, the count is m / p. So far, so good. Now, the idea of the other part is that the count of numbers not exceeding m that are divisible by p or one of the later primes is

count_multiples_of_p + count_multiples_of_other - count_multiples_of_p_and_other

which so far is correct. But your implementation supposes

count_multiples_of_p_and_other = count_multiples_of_other / p

which is only asymptotically correct. Consider for example the three primes [2, 3, 5] and m = 20.

Your function returns

F([2,3,5], 20) = 20/2 + F([3,5], 20) - F([3,5], 20)/2
    -- F([3,5], 20) = 20/3 + 20/5 - (20/5)/3 = 6 + 4 - 1 = 9
               = 10 + 9 - (9/2) = 10 + 9 - 4 = 15

But if you count, there are six numbers <= 20 not divisible by any of the three primes, 1, 7, 11, 13, 17, 19, so only 14 that are multiples of any of the three.

The correct way to account for the multiples of p and any of the later primes is to count the multiples of any of the later primes not exceeding m/p, because if k is a multiple of p as well as at least one of the later primes, then k/p is a multiple of one of the later primes that doesn't exceed m/p.

So the fix to your function consists simply of moving a parenthesis (well, two, since you have so many),

int f(int *factors, int start, int nf, int m) //nf=no. of factors, start=0, m=M
{
    if(start == nf-1) 
        return (m / factors[start]);

    return (m / factors[start]) + f(factors, (start + 1), nf, m)
              - ((f(factors, (start + 1), nf, m /* )) */ / factors[start]) ));
    //                                          ^^^^^^^^                   ^^
}

(and you have several superfluous pairs of parentheses, you might consider removing some of them).

1
  • Thank you very much.Your explanation is really good and helpful. Oct 12, 2012 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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