SOME SIMPLE MATHEMATICS USED IN COMPETITIVE PROGRAMMING

 PRIME NUMBERS:

1. A number n is prime if it has only two factors 1 and n. The non prime numbers have prime factors between 1 to sqrt(n). So, to check if a number is prime or not, we have to check for each number less than sqrt(n), if there is a number that divides n, then n is not a prime otherwise it is a prime.

2. Approximate number of prime numbers from 1 to n can be estimated from the formula:

                    no of primes= n/(ln n)

            This is useful while looking for time complexity in various problems.

3. A number n has O(log n) number of prime factors.

 SIEVE OF ERATOSTHENES:

It is an algorithm to construct an array sieve which allows us to efficiently check if a number x between 1 to n is prime or not will time complexity O(n log n)

Let the boolean array be sieve [n], then sieve [x] will be true if it is a prime else it will be false. Initially all the elements are taken as 0.  If an integer x is prime then all the integers 2*x, 3*x, 4*x .......will not be prime.

The pseudocode is as follows:

void sieveof (n)

{

            bool sieve [n];

            memset( sieve, true, sizeof(sieve);

            for(int i=2; i*i<=n ;i++)

            {

                if( sieve[i]==true)

                {

                    for(int j=2*i; j<=n;j+=i)        

                        {

                                sieve[j]=false;

                        }

                }

            }

            //printing all primes

           for(int i=2, i<=n;i++)

            {

                    if(sieve[i]==true)

                        cout<< i<<endl;

             }

}

RUNNING TIME OF SIEVE CODE FOR DIFFERENT CONSTRAINTS

UPPER BOUND (n)	TIME (s)
10^6	0.01
2*10^6	0.03
4*10^6	0.07
8*10^6	0.14
16*10^6	0.28
32*10^6	0.57
64*10^6	1.16
128*10^6	2.35

 

We can also find the smallest prime factorization of all number up to n using the sieve code with time complexity O (n log log n) [approx. O(n) ].  The pseudocode for this purpose can be as follows:

int smallprimefact[n];

void sieve() 

{ 

    smallprimefact[1]=1; 

    for(int i=2;i<n;i++) 

  

       {

        // marking smallest prime factor for all number to be itself. 

        smallprimefact[i] = i; 

       }

  

    // separately marking smallest prime factor for every even number as 2 

    for (int i=4;i<n;i+=2) 

        smallprimefact[i]=2; 

  

    for (int i=3;i*i<n; i++) 

    { 

        // checking if i is prime 

        if (smallprimefact[i]== i) 

        { 

            // marking smallest prime factor for all numbers divisible by i 

            for (int j=i*i;j<n;j+=i) 

  

                // marking smallprimefact[j] if it is not previously marked 

                if (smallprimefact[j]==j) 

                    smallprimefact[j] = i; 

        } 

    } 

} 

The function for  returning prime factorization of x by dividing by smallest prime factor at every step is shown below which has time complexity O (log n).

vector<int> getfactorization(int x) 

{ 

    vector<int>v ; 

    while(x!=1) 

    { 

        v.push_back(smallprimefact[x]); 

        x=x/smallprimefact[x]; 

    } 

    return v; 

} 

LCM AND GCD:

1. The relation between gcd of a and b and lcm of a and b is- lcm(a,b)=(a*b)/(gcd(a,b))

2. Euclid's algorithm to find gcd :

        gcd ( a,b)= a         if b=0

        gcd (a,b )= gcd ( b, a mod b )             if b!=0

Pseudo code for this algorithm is \

 gcd ( a, b )

{

    if (b==0) 

    return a;             //initialization of the recursive code

    else

    return  gcd ( b, a%b );

}

Time complexity is O( log n )  , n is the min (a,b).

3. Using Extended  Euclid's algorithm we can find two numbers x and y such that

     a*x + b*y= gcd (a,b)

      Pseudocode can be as follows:

       tuple<int,int,int> gcd(int a, int b) 

        {

             if (b == 0) 

            { return {1,0,a}; } 

            else 

            { 

                int x,y,g; 

                tie(x,y,g) = gcd(b,a%b); 

                 return {y,x-(a/b)*y,g};

               }

          }

Source : GUIDE TO COMPETITIVE PROGRAMMING

 MODULAR EXPONENTIATION:

To find the value of  x^n mod m in log n time complexity, we can use the following key concept.

x^n= x^(n/2) * x^(n/2)             if n is even

x^n= 1                                        if n is zero

x^n= x^(n-1) * x                        if n is odd

The pseudocode can be as follows:

int modpower( int n, int x, int m)

{

  if(n==0) 

    return 1%m;        //initialization

 long long y= modpower ( n/2 , x, m);

   y= ( y*y) % m;

    if (n%2 !=0)

    y=( y*x)%m;

return y;

}

EULER'S FORMULA:

Two integers a and b are called coprime if gcd(a, b) = 1. Euler’s totient function ϕ(n) gives the number of integers between 1 ... n that are coprime to n. Any value of ϕ(n) can be calculated from the prime factorization of n using the formula ϕ(n) = [ p1^(a1-1)* (p1-1)] *[ p2^(a2-1)* (p2-1)]  *........................*[ pn^(an-1)* (pn-1)]   . 

For example, since 10 = 2 · 5,  

ϕ(10) = 2^0 · (2 − 1) · 5^0 · (5 − 1) = 4.

1. (x^ϕ(m)) mod m = 1

2. For prime number m, x^(m−1)mod m = 1.

3. x^n mod m = x^(n mod (m−1)) mod m, if m prime [ can be used to calculate x^n for large x ].