I have been reading a competitive programming book for one month. The book is written by one of the world finalists of our country (Bangladesh). Point to be noted, the book is written in our native language (Bengali) and that is not so popular worldwide. Because of having the content in Bengali I can't refer it here. That's why I am sorry first of all.
In Number theory chapter of that book, there are given many algorithms to test Primality. The most optimal he has shown, is "Sieve of Eratosthenes" in O(nloglogn). But he wrote one line. I am translating it. "There is a more efficient method of testing primality in O(logn). Think it yourself. And if you are undone, just google it!!"
I have googled about it.But I didn't find anything satisfactory.
Is it really possible to test the primality of a number in O(logn) ?? And if it is possible then up to which range it can be concluded ??
The statement is incorrect. For a number N, the number of digits is O(log N), so the statement means that there is an algorithm that's linear in the number of digits. The best known result is polynomial in the number of digits. (Agrawal–Kayal–Saxena primality test, Õ(logN 12). That's logN to the power of twelve, not one.
Still, Õ(logN 12) ⊂ O(N)