What is Primality test?
Primality test is an algorithm used to determine if a number is prime or not.
One of the basic algorithm used is given below:
Its time complexity is O(√n), and space complexity is O(1).
Suppose n is greater than 10^20 ie out of range of the long long int , the largest container of c++ in terms of size(8 bytes).
In this case the mentioned algo will indeed perform poorly. Therefore we must have some techinque/algorithm to counter bigger numbers.
No comments:
Post a Comment