The idea here is to check whether each and every number from 2 till half of that number [2, n/2] divides the number or not. If any of them divides the number without leaving any remainder, we can declare that the number is NOT a prime number. If no number in that range divides properly, the number is called a Prime number. We check only till n/2, because 2 * n/2 would be n, there would be no number greater than n/2 would divide n properly. In the worst case, It needs n/2 iterations to confirm whether the number is prime or not. In our case, for 101, it is 50.

The simplicity of this algorithm would tempt us to use this always. Lets see, if we can improve this. If we observe closely, if the number n is odd, we don't even have to try any of the even numbers. This would reduce the number of iterations needed by half.

As we can clearly see, if n is even it can not be a prime number, since if a number is even it is divisible by 2. So we check only the odd numbers starting from 3 till n/2 and we are skipping all the even number  by incrementing the loop's index variable by 2 every time. So the loop would be run for the values 3,5,7,9, 11... Now if we look at the performance of this approach, we just need n/4 iterations to find whether the number is a prime number or not. In our case, for 101, it is 25.

Lets see, if we can reduce it further from n/4. Lets write down the combinations which would yield 100. {2, 50}, {4, 25}, {5, 20} and {10, 10}. Lets try 256. {2, 128}, {4, 64}, {8, 32}, {16, 16}. In both the cases, atleast one of the numbers is always lesser than equal to the square root of the actual number. (I, honestly, don't know how to prove this, but this observation works always). So, instead of looping till n/2 we are going to limit the loop at square root of the number. Combining the observation we made in approach 2, presenting approach 3.

We have already had good performance with approach 3. Lets see if we still can improve it. Lets list the four values with which we may need to divide 101 to determine whether it is prime or not. The values are {2, 3, 5, 7, 9}. We have 2 as well here, since we check whether the input is even or not and 11 is not included because sqrt (101) would be rounded off to 10. The odd item in the list is 9, since we are checking against all the odd number between 2 and sqrt(n). We all know that, any given composite (non-prime) number can be expressed in terms of its prime factors. So we can try and divide the number only with the prime numbers within the range [2, sqrt(n)]. Note: This approach works only when we have a predetermined list of prime numbers. If we don't have that its better to stick to approach 3 or have a look at approach 5 below.

Lets observe the list the prime numbers a bit.

{2, 3, 6*1-1, 6*1+1, 6*2-1  6*2+1  6*3-1  6*3+1  6*4-1  6*5-1  6*5+1  6*6+1  6*7-1  6*7+1,  6*8-1  6*9-1, 6*10-1, 6*10+1, 6*11+1, 6*12-1, 6*12+1, 6*13-1, 6*14-1, 6*15-1, 6*16+1, 6*17-1...}

Based on the ideas discussed above, I managed to solved the SPOJ's PRIME1 problem. The problem description can be found here http://www.spoj.pl/problems/PRIME1/

Spoiler alert: This http://ideone.com/4n9kB has my solution to the above mentioned PRIME1 problem.