Primes: Primality Testing,Generating Primes ( Sieve of Eratosthenes)

Prime Numbers:
All numbers greater than 1 and having only two divisors (1 and the number itself) is called prime numbers.
Such that 2,3,5 are prime. 4,8,10 are not.

Primality Testing:

In this section we will discuss how to check whether a number is prime or not.

We can iterate from 2 to n-1 and checks if the number can be divided by any of these numbers.But these approach has a complexity of O(n).
We can notice that for every number it is impossible to have a divisor greater than n/2 besides the number itself. So it is enough to iterate over 2 to n/2. But though the complexity does not improve a much.

So we will discuss about a property that will allow us to reduce the complexity upto square root of n,Using the knowledge from discrete math- " if a number is not prime then there exists at least one prime divisor of that number which is less than square root of n."

So using this property we only need to iterate over 2 to sqrt(n). Thus our approach is reduced to the complexity of O(sqrt(n)).

Code:
bool isPrime(int n)
{
int f=1;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
f=0;
break;
}
}
return f;
}

Here I use i*i<=n which is an alternate to i<= sqrt(n).
But sqrt(n) function has a complexity of O(sqrt(n)),
So i will suggest not to use the function in loop, 
which will unnecessarily increase the run time
of the code. Besides there can also be a floating
point precision error if written like that. So better 
way to compute the square root of n in a variable before 
and then use that variable or simply use the above method
I used in the code.

Generating Prime:

Ok for Generating primes, a very good article was
written by Jane Alam Jan in Lightoj. The article is so enriched,
I found no need of writing
anything else :) .

Code I Used:

#define M 1000000 bool marked[M]; vector <int> primes; void sieve(int n) { primes.push_back(2); for (int i = 3; i * i <= n; i += 2) { if (marked[i] == 0) { primes.push_back(i); for (int j = i * i; j <= n; j += i + i) { marked[j] = 1; } } } }

Complexity:

The algorithm has run time complexity of O(Nlog(logN))




Solving Linear Diophantine equation

This post would be a sequel. one can find the previous post here.

Before we proceed further we look into a variation, sometimes if the equation looks like this
11*x + 2 = 16 [mod 26] and asks to solve for x, we would just simplify the equation as follows:

11*x = 14 [mod 26]
=> x = (11)^-1 * 14 [mod 26]
Then we proceed as the standard procedure goes, find the (11)^-1 [mod 26] and replace the value in equation and solve for x.

In this post we would see linear Diophantine equation and its solve method using extended euclidean algorithm.

A * x + B * y = 1 ......... [equation having this form is called linear Diophantine Equation]

The condition for having a solution of this equation is GCD(A,B) must be equal to 1.

now suppose we have this equation 47*x + 30*y =1 ........ (first)

as GCD(47,30)=1 , so solution exists.

Now we will follow the same procedure we used for finding modular inverse:

47 = 30*(1) + 17 ...................(1)
30 = 17*(1) + 13 ...................(2)
17 = 13*(1) + 4   ...................(3)
13 = 4*(3) + 1    ....................(4)

form the last equation, solve for remainders,then backwardly substituting values of remainders in the previous equations we get,

17 = 47 + 30*(-1)
13 = 30 + 17*(-1)
4 = 17 + 13*(-1)
1 = 13 + 4*(-3)

now backward....

1 = 13 + [17 + 13*(-1)]*(-3)
   = 13 + 17*(-3) + 13*(3)
   = 13*(4) + 17*(-3)
   = [30 + 17*(-1)]*(4) + 17*(-3)
   = 30 *(4) + 17*(-4) + 17*(-3)
   = 30*(4) + 17*(-7)
   = 30*(4) + [ 47 + 30*(-1)] * (-7)
   = 30*(4) + 47*(-7) + 30*(7)
   = 47*(-7) + 30*(11)

so we get , 47*(-7) + 30*(11)=1
comparing with our primitive equation, x= -7 and y=11 ...

A slight variation: when the right side of our Diophantine equation is not equal to 1

form: A*x + B*y = C

condition of having a solution is GCD(A,B) must be equal to one and
if C % GCD(A,B) is equal to 0 then there exists a solution.

Solution:
1. first solve A*x + B*y = 1
2.then multiply both side by C/GCD(A,B) , this will give us trivial solution.
3. suppose x and y is primary solution got in the step 2, then other solutions can be obtained from these equations for different values of t:
X= x + B/gcd(A,B) * t
Y= y + A/gcd(A,B) *t

Extended Euclidean Algorithm implementation:

typedef pair <int,int>pii;

pii ext_euclid(long long int a,long long int b)
{
    if(a<b)
        return ext_euclid(b,a);
    if(b==0)
        return pii(1,0);
    else
    {
        pii temp= ext_euclid(b,a%b);
        return pii(d.ss, d.ff-d.ss*(a/b));
    }
}

Modular Inverse implementation:

int mod_inverse(int a,int n)
{
     pii ret = ext_euclid(a,n);
return ((ret.ff % n ) + n ) % n;
}

Modular Inverse : Mathematical Approach

Modular Inverse is an important topic in number theory. To understand modular inverse one has to know basics of modular arithmetic or congruence which in this post I will skip. one might find this helpful for the basic . we would discuss a bit(a tiny bit though :P ) advanced thing here.

sometimes we need to find (a/b)% mod . we can simplify this as follows:

(a/b)% mod = ( a% mod * b^-1 % mod) % mod

here b^-1 % mod = modular inverse of b

we can find this modular inverse by extended euclidean algorithm (or also by big mod algorithm using Euler's theorem if mod is prime).Anyway at first let's check how mathematically modular inverse is calculated:

suppose we want to find modular inverse of 27 mod 392.

dividend = divisor (quotient) + remainder
392         =  27*(14)                 + 14 ......................... (1)
27           = 14*(1)                    + 13 ..........................(2)
14           = 13*(1)                    + 1 ............................(3)

every time divisor is becoming dividend and remainder is becoming divisor except in the first step.

Now form the last equation, we would solve for remainders, just doing side changing,

1 = 14 + 13*(-1) ....................(4)
13 = 27 + 14*(-1) ....................(5)
14= 392 + 27*(-14) ....................(6)

we can backwardly substitute values of remainders in the previous equation (4).

1 = 14 + [27 + 14 * (-1)] * (-1) ................. // just replacing values of 13 from equation (5)
=>1= 14 + 27*(-1) + 14(1)
=> 1 = 14*(2) + 27 *(-1)

Now again we can replace the values of 14 from the equation (6) in the same procedure,

1 = [392 + 27*(-14)] * (2) + 27*(-1)
=>1 = 392*(2) + 27*(-28) + 27*(-1)
=>1 =392*(2) + 27*(-29) .................... (7)

we can recall we are calculating modular inverse of 27 mod 392,so if we mod equation (7) by 392
we get,

392%392=0 and -29 % 392= 363

replacing these values in (7)

1= 0 + 27*(363)

=> 27*(363)= 1 (mod 392)

so 27^-1 = 363 (mod 392)


Before advancing to code for calculating the modular inverse one must know the math behind it.