Mathematical Problems in Algorithms (Summary)

Source: http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/mathematics-for-topcoders/

1: Prime Check

public boolean isPrime (int n)
{
   if (n<=1) return false;
   if (n==2) return true;
   if (n%2==0) return false;
   int m=Math.sqrt(n);

   for (int i=3; i<=m; i+=2)
      if (n%i==0)
         return false;

   return true;
}

2: Get All Primes

public boolean[] sieve(int n)
{
   boolean[] prime=new boolean[n+1];
   Arrays.fill(prime,true);
   prime[0]=false;
   prime[1]=false;
   int m=Math.sqrt(n);

   for (int i=2; i<=m; i++)
      if (prime[i])
         for (int k=i*i; k<=n; k+=i)
            prime[k]=false;

   return prime;
}

3: greatest common divisor (GCD)

Euclid's algorithm 

//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
} 

4: lowest common multiple (LCM)

public int LCM(int a, int b)
{
   return b*a/GCD(a,b);
}

5: Rectangles Overlap

Suppose we have two rectangles R1 and R2. Let (x1, y1) be the location 
of the bottom-left corner of R1 and (x2, y2) be the location of its 
top-right corner. Similarly, let (x3, y3) and (x4, y4) be the respective
 corner locations for R2. The intersection of R1 and R2 will be a 
rectangle R3 whose bottom-left corner is at (max(x1, x3), max(y1, y3)) 
and top-right corner at (min(x2, x4), min(y2, y4)). If max(x1, x3) > 
min(x2, x4) or max(y1, y3) > min(y2, y4) then R3 does not exist, ie 
R1 and R2 do not intersect. 

6: Fractions

public int[] multiplyFractions(int[] a, int[] b)
{
   int[] c={a[0]*b[0], a[1]*b[1]};
   return c;
}