to calculate the number of integers co-prime to N and less than N we can simply calculate its ETF . However to calcuate the number of integers co-prime to N but less then M where M < N , how can we modify / calculate it ? I have tried the code to calcuate the ETF but can't proceed how to modify it to get the required result.
Code:
int etf(int n)
{
int result = n;
int i;
for(i=2;i*i <= n;i++)
{
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}
Thanks
See Question&Answers more detail:os