Primality Test – Naive Methods

forthright48 on July 8, 2015

Problem

Given a number N, determine if it is a prime.

What is a Prime Number?

A prime number is a positive number greater than 1 which has no positive divisor except for 1 and itself. For example, 2, 3, 5, 11 are prime numbers. Whereas 4, 6 are non-prime or composite numbers.

O(N) Solution

From the definition, we can easily construct a Primality Test function that can determine if a given number N is prime or not. Let us call it isPrime() function.

bool isPrime ( int n ) {
    if ( n <= 1 ) return false; // n needs to be greater than 1
    for ( int i = 2; i < n; i++ ) {
        // If it is possible to divide n with a number other than 1 and n, then it is not prime
        if ( n % i == 0 ) return false;
    }
    return true; // Otherwise, this is prime
}

The code simply iterates over all values between 2 and N-1 and checks if it can divide N. It has a complexity of O(N).

Read More

Lowest Common Multiple of Two Number

forthright48 on July 7, 2015

Problem

Given two number A and B, find their lowest common multiple (LCM).

We are trying to find the LCM of A and B. What is LCM? It is the smallest positive number which is divisible by both A and B.

How do we find it?

It is based on the formula that, $LCM(A,B) \times GCD(A,B) = A \times B$. How did we get this formula? I will discuss it another day. It’s not that hard to figure out though. Anyways, from that formula we can derive $LCM(A,B) = \frac{A \times B}{GCD(A,B)}$.

For example, $LCM(6,15) = \frac {(6 \times 15 )}{GCD(6,15)}= \frac{90}{3} = 30$, $LCM(3,4)= \frac{3 \times 4 }{GCD(3,4)} = \frac{12}{1} = 12$.

Code and Pitfalls

Let us try to convert the above equation for LCM to code. If we convert exactly like the equation, code would be something like the following:

int lcm ( int a, int b ) {
    return ( a * b ) / gcd ( a, b );
}

This will work, but for some cases, this code will overflow. For example, if we try to find $LCM( 2^{20}, 2^{15})$, it is obvious that the LCM is $2^{20}$. But notice what happens when we follow the algorithm. We first try to multiply $2^{20}$ with $2^{15}$, which results in $2^{35}$ which is too big to fit in an int variable. It overflows and returns us wrong answer. But the LCM itself should fit in the “int” variable easily.

A better way to write the above code is using the following observation. $LCM(A,B) = \frac{A \times B}{GCD(A,B)} = \frac{A}{GCD(A,B)} \times B$. Since $GCD(A,B)$ divides both A and B, the fraction $\frac{A}{GCD(A,B)}$ will be an integer. This alternate equation avoids overflow since instead of multiplying A and B, it first reduces A to a smaller number and multiplies the resultant number with B. So, if $LCM(A,B)$ fits in int variable, then we will get it without the risk of intermediate products overflowing.

int lcm ( int a, int b ) {
    return ( a / gcd ( a, b ) ) * b;
}

Related Problems

  1. UVA 11388 – GCD LCM (Analysis)

Euclidean Algorithm – Greatest Common Divisor

forthright48 on July 1, 2015

Problem

Given two number A and B, find the greatest number that divides both A and B.

What we are trying to find here is the Greatest Common Divisor(GCD) of A and B. What is GCD? Like the name suggests, it the largest number ( let that be G ), that can divide both A and B. For example, $GCD(2,8) = 2$, $GCD(3,4) = 1$, $GCD(12,15) = 3$.

How do we find it?

There are many ways. One way is to list down all the divisors of A and B and then find the largest common divisors from those two lists. This is a naive method and takes too much time.

Another approach is to use Euclidean Algorithm, that 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. And of course, we can apply the principle to the smaller states repeatedly until the state becomes trivial. The two trivial states for GCD are $GCD(a,a) = a$ and $GCD(a,0) = a$.

Read More