give the most optimised code for checking whether a number is prime or not?
Most optimised code
Hey @Rj.25 if you are checking if a given number is prime or not recommended method is to iterate till square root of number and check if the given number is divisible by any of those number or not. If you have to perform primality test on multiple numbers it is recommended to construct sieve of eratosthenesand then check if the given number is prime or not.
Other than these methods we can also use Fermat Primality Test which is based on fermat’s little theorem. The theorem states that, given a prime number P, and any number a (where 0<a<p), then
a^n-1 ≡ 1 (mod n)
OR
a^n-1 % n = 1
Furthermore based on Fermat’s primality test we have an probabilistic test called Miller-Rabin Primality Testing.
You can read more about the methods mentioned above here: https://www.hackerearth.com/practice/math/number-theory/primality-tests/tutorial/
If you are interested in knowing more advanced methods please refer to this https://math.stackexchange.com/questions/897241/fastest-way-to-find-if-a-given-number-is-prime/897442
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.