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.

Sieve of Erathronese using Byte Array

(bit manipulation)

 Sieve of erathronese is a easy marking technique for finding prime numbers in less time.Using byte array for checking and marking of prime numbers increases space complexity as well as time complexity (as bit manipulations are fast). Using byte array 1 integer can be used to store 32 numbers.

Following code prints prime numbers upto 32000:

#include <iostream>
 
int arr[10000];
#define set(i) (arr[i>>5]|=(1<<(i&31)))
#define is_compound(i) (arr[i>>5]&(1<<(i&31)))

using namespace std;

int main()
{
    for(int i=3;i<32000;i+=2)
    {
        if(!is_compound(i))
        {
            int k=2*i;
            for(int j=i*i;j<32000;j+=k) set(j);
        }
    }

    cout<<2<<" ";
    for(int i=3;i<32000;i+=2) if(!is_compound(i)) cout<<i<<" ";
    cout<<endl;
}

Code is pretty straightforward. We have skipped even numbers for increasing time complexity.