Programming Basic Mathematics Concepts

Basic Mathematics:

Mathematics is almost synonymous to Computers. Computer word itself comes from the word "Compute", which means to calculate.

In every competitive programming contest, you  will see at-least one problem on basic mathematics. Such problems are easy to crack in very less time with almost 100% accuracy, of course one must have maths concepts clear in one's mind.

So let's start....

In this post, we will learn about Number Theory : Prime Numbers:

What are prime numbers:

A natural number starting from 2: {2, 3, 4, . . .} is considered as a prime if it is only divisible by
1 or itself. The first (and the only even) prime is 2. The next prime numbers are: 3, 5, 7, 11, 13,
17, 19, 23, 29, . . . , and infinitely many more primes.

Good to remember stats:

• There are 25 primes in the range [0..100]
• 168 primes in the range [0..1000]

First Program:

Q) To test whether a given natural number is prime or not?  

     Method Signature:  bool isPrime(int n) {}

Soln.)
       i) Naive approach would be is to test by definition of prime number:

            public static bool isPrime(int n)
        {
            bool result = true;
            for (int i = 2; i < n; i++)
            {
                if (n % i == 0)
                {
                    result = false;
                }

            }
            return result;
        }

This approach runs in O(n), in terms of number of divisions. Performance can be improved.

ii) The first improvement is to test if N is divisible by a divisor ∈ [2 . . .√N], i.e. we stop when
the divisor is already greater than √N. This is because if N is divisible by p, then N = p × q. If
q were smaller than p, then q or a prime factor of q would have divided N earlier. This approach runs in O(√N).

iii)  The second improvement is to test if N is divisible by divisor ∈ [3, 5, 7 . . .√N], i.e. we only
test odd numbers up to √N. This is because there is only one even prime number, i.e. number 2,
which can be tested separately. This is O(√N/2), which is also O(√N).

iv) The third improvement is to test if N is divisible by prime divisors ≤ √N. This is because if a prime number X cannot divide N, then there is no point testing whether multiples of X divide N or not. This is faster than O(√N) which is about O(|#primes ≤ √N|). For example, there are 500 odd numbers in [1 . . . Sqrt(1000000)], but there are only 168 primes in the same range. The number of primes ≤ M – denoted by π(M) – is bounded by O(M/(ln(M) − 1)), so the complexity of this prime testing function is about O(√N/ln(√N)).

To implement (iv) solution, we need a fast algorithm to generate the list of prime numbers, which we will learn in my next post and then i will give you the code.

Many Thanks,

Cheers!