Its wonderful how such an apparently trivial problem of finding prime numbers is turning into such an animated discussion on various algorithmic techniques - each with its own benefits & pitfalls!
Wikipedia's page on the prime number is as exhaustive as its page on human evolution! It just goes to show how fascinating Mathematics is that it throws a challenge in something as apparently simple as finding primes.
It also demonstrates the importance of algorithmic design & analysis for effective computing - even the biggest super-computer on the planet cannot achieve its true computational potential if the algorithm involves excessive looping or is inefficient!
Also, a special thanks to Niraj (friendsofniraj), who has given an extremely succint explanation of how the Square Root logic works - there was no need for me to read a single word on Wiki about the algorithm (although I did to satiate my curiosity - and might I say, it is very thoroughly dissected in Wikipedia!) And also the keen eye of Shabbir noticed the redundancy in the calculation of Square Root through the inner-loop!
All in all - a very fascinating discussion!