Better Algorithm for Prime Number Checking

I have been thinking of some of the traditional algorithms which we learn during our Programming Language study. One of the most important one is the Prime Number checking.

The Traditional Algorithm checks if the given number is divisible by numbers ranging from 2 to the square root of that number (or some times to half of the number). This algorithm is fast. But, I have figured out a better one.

My Approach was very simple. I worked on the some of the drawbacks of the algorithm.

1. If the Number is the square of a Prime Number :  Consider the case when the number is the square of a prime number. Eg. : 121. So, the algorithm has to check the numbers 2,3,4,5,6,7,8,9,10, and finally 11 to know that 121 is not a prime number.
2. Once we checked with 2, then why check again with even numbers? :  Second thought was, once, we have already checked with the number 2, then you should we again check with other even  numbers?

So, I derived an algorithm for Prime-Number checking. It gives the result in O(1) time, in case of Square of Prime Numbers, and uses half the time, in average cases.

Algorithm:

function isPrime(n):

 1 : check if n is divisible by 2

     1.1 : if yes, return false // n is even

 2 : check if n is divisible by square root of n (integer value)

     2.1 : if yes, return false // n has perfect square root

 3 : set i <- 3

 4 : continue until i < sqrt (n)

     4.1 : check if n divisible by i

           4.1.1 : if yes, return false

     4.2 : increment i by 2; ie. i = i+2 (next odd number)

 5: return true // at this stage, the number will be prime

We can still optimize this algorithm for large numbers, using Dynamic Programming methods. But, I feel this is a better algorithm, to be taught for the beginners.