Finding Number of Coprimes Less Than Certain Number

(Coprimes of n less than m)

Calculating coprimes of a number less than that number i.e. totient function of a number is easy by some easy tricks.

Suppose we are given a numbers n & m such that m<n and we have to calculate coprimes of n which are less than n. This can also be solved with a simple trick of inclusion-exclusion principle.

To calculate coprimes of n less than m, we first calculate numbers less than m which are not coprimes to n and then subtract it from m.

For example, we have to find coprimes of 30 less than 20.
Now prime factors of 30 are 2,3,5. To find non-coprime numbers of 30 less than 20, we find number of multiples of 2,3 & 5 less than 20.

Number of multiples of 2 = 20/2 = 10
Number of multiples of 3 = 20/3 = 6
Number of multiples of 5 = 20/5 = 4

Total multiples = 10+6+4 =20

But, here some multiples of 2 & 3 are repeated.
Number of repeated multiples of 2 & 3 = 20/(2*3) = 20/6 = 3

Similarly,
Number of repeated multiples of 2 & 5 = 20/(2*5) = 20/10 =2
Number of repeated multiples of 3 & 5 = 20/(3*5) = 20/15 = 1

Now, extra deleted multiples are
Number of repeated multiples of 2,3&5 = 20/(2*3*5) = 20/30 =0

So, number of multiples of 2,3,5 less than 20= 10+6+4-3-2-1+0 = 14

Hence, number of non-coprimes of 30 less than 20 = 14

and number of coprimes of 30 less than 20 = 20-14 = 6
(which are 1, 7, 11, 13, 17 and 19)

This method is application of inclusion-exclusion principle. It can be implemented in code using recursive funcion.

Following code can be used for finding above:

#include<stdio.h>
#include<math.h>
 
/*Start of code for  storing prime numbers upto 100000 (sieve using byte array)*/
 
int *Prime[100000>>5];
int pos[9594];                                      //stores prime numbers
#define prime(i) ((Prime[i>>5])&(1<<(i&(31))))
#define set(j) (Prime[j>>5]|=(1<<(j&(31))))
#define LIM 100000
#define SLIM 317

int sieve()
{
        int i, j, m, n, t,x,k,l,h;
        set(1);
        pos[1]=2;
        pos[2]=3;
        for(k=2,l=3,i=5; i<=SLIM; k++,i=3*k-(k&1)-1)
                if(prime(k)==0)
                {
                        pos[l++]=i;
                        for(j=i*i,h=((j+2)/3); j<=LIM; h+=(k&1)?(h&1?((k<<2)-3):((k<<1)-1)):(h&1?((k<<1)-1):((k<<2)-1)),j=3*h-(h&1)-1);
                        set(h);
                }

        i=3*k-(k&1)-1;

        for(; i<=LIM; k++,i=3*k-(k&1)-1)
        if(prime(k)==0)
        {pos[l++] = i;isPrime[i]=true;}

        return l;
}
//End of code for prime numbers 
 
int coprimes(int *factors,int start,int nf,int m) //calcualates  multiples less than m
{

    int sum=0;

    if(start==nf-1) return (m/factors[start]);

    return

      (m/factors[start]+coprimes(factors,(start+1),nf,m) - coprimes(factors,(start+1),nf,m/factors[start]));

}

int main() { 
 
        int x=sieve();
        int n,m;

        scanf("%d %d",&n,&m);
        int i,nf=0;         //nf is number of prime factors

        int factors[17];   //stores prime factors of n
 
        for(i=1;pos[i]<=m;i++)
        {
            if(n%pos[i]==0) {factors[nf++]=pos[i];}
        }

        if(nf==0) printf("%d\n\n",m);
 
        else
       {
        int lim=coprimes(factors,0,nf,m);
        printf("%d\n\n",m-lim);
       }
    }
         return 0;
}

Here, first we find all prime numbers upto 100000 so that it is easy to calculate prime factors of number. For this, I used sieve of erathronese using byte array. Also, multiples of 2 and 3 are skipped in the sieve to increase time complexity.
Prime factors are stored in array factors.
Then recursive function coprimes is called and finally answer is printed.