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))




Least Common Multiple of Two Numbers

Given Two numbers, say a and b we have to find their lowest multiple which is common to the both nunbers.

Finding Method:
The formula is:
GCD(a,b) * LCM(a,b) = a * b;
Therefore, LCM(a,b) = (a * b) / GCD(a,b);

Code and pitfalls:
int lcm(int a,int b)
{
      return ( a * b ) / gcd ( a, b );
}

this code will work fine but for some cases it may overflow.So we should rewrite the (a*b)/gcd(a,b) part into a/gcd(a,b) * b .

What I use:

template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); }

Greatest Common Divisor

So we are trying to compute GCD ( Greatest Common Divisor) of two numbers, Say a and b.As the name suggests we are trying to determine the greatest number that divides both a and b.

Finding Procedure:
There are many procedures of how we can find the gcd of two numbers, but we will discuss about the euclidean method here.

It works on the principle GCD(a,b)=GCD(b,a%b). Since GCD(b,a%b) is a smaller state,it is easier to find than the original.So we can solve it using this recursion relation and using the base case, GCD(a,a)=a and GCD(a,0)=a;

Code:
Recursive version:
int gcd ( int a, int b )
{
    if(b==0) return a;
    return gcd(b,a%b);
}

Iterative Version:
int gcd ( int a , int b )
{
    while(!b)
    {
        a=a%b;
        swap(a,b)
     }
}

Built in version:
There is also a builtin version in C++ for finding GCD. ( __gcd(a,b) ).

What i use:
I use this as my template:
template< class T > T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
Proof:
We can imagine a grid a * b. We are trying to find the largest number x 
such that we can cover the whole grid using tiles of size x * x . 
And if the whole grid is to be covered by the square sized tiles so x
must be a divisor of both a and b. So we will try to choose x such that x
be the smaller number between a and b (say b). If we found that it is not
possible to cover the whole grid, there must be some remainder of the grid
which will be a%b. So the we will try the same method for a= b and b=a%b;




GCD texure: courtesy Wiki.


Complexity:
Well the complexity of this algorithm is kindaa tricky, My coach refers me to an answer of stack overflow. For now I am only giving the complexity of the answer.but as soon as i understand the proof the solution i will rewrite this portion.
The complexity of above algorithm is - O( log10(a) + log10(b) ).

Coding Pitfalls:
Well this is one of the great things i have learnt recently from my Coach.Though i used the algorithm for a long time i didn't know this pitfall.That is the algorithm only works for non negative numbers. So in case of negative numbers are concerned we can either send absolute value of the numbers or we can take the absolute value of the result.

Another thing is- notice that 
GCD(0,0)=0. It should be infinity. Also, if you try to work with the return value of GCD(0,0), then you might get RTE due to division by zero.

Number Theory From Scratch to Things I know

This Blog Post will be updated time to time. I will update when I think I have learnt something new and need to keep note. In this post I will mainly focus on theory along with code.
Though working code for my cookbook will be also updated in Dropbox and google drive as well.

1.Greatest Common Divisor.
2.Least Common Multiple of Two Numbers.
3.Primes: Primality Testing,Generating Primes ( Sieve of Eratosthenes).