Wednesday, May 14, 2014

a bit of array

Algorithm attempts to solve problems through manipulation of data structures, hence data structure and algorithm go hand in hand. They are like Batman and Robin, only less gay (just saying).

One of the most fundamental data structure in any programming platform is array. When we initialize an array, especially in case of static array, we are allocating a fixed amount of blocks of memory to a certain data type, which are accessible by indicating the specific index of the array. The strength of an array structure is that by knowing the index, access operation on arrays takes O(1) time. However, since the size of arrays have to be known before use, there are chances of excessive unused memory allocated which results in lower performance.

Here is one interesting manipulation of array. Consider a problem of printing all prime numbers less than 50,000. A prime number is defined as a number which can only be divided by itself and 1. (Interestingly, 1 is not a prime ladies and gentlemen!)

A simple approach to this problem can be described as follows. For any number between 0 to 50,000, test whether it is prime, then print it. If a number is divisible by any number less than itself (excluding 1), than it is not a prime. Otherwise, we have a prime number.

Here is an interesting implementation of this idea, leveraging on the fact that if a number is a product of two other numbers (excluding 1), then it is not a prime.

#include <stdio.h>
#define N 10000

int main(){
  bool a[N]; //for number 1 to 49,999,a[i]=1 if prime, 0 otherwise
  for(int i=2;i<N;++i)a[i]=1; //initialize a[i]
  for(int i=2;i<=N/2;++i){
    for(int j=2;j<=N/i;++j){ //leveraging on symmetry of i*j
      a[i*j]=0; //not prime!
    }
  printf("Primes less than 10,000 are: ");
  for(int i=2;i<=N;++i){
    if(a[i])printf("%d ",a[i]);
  }
  printf("\n");
  return 0;
}

Leveraging on symmetry of i*j allows us to only check the value of i from 2 to N/2. j must be less than N/i since we are only interested in values of  i*j that are less than N.