Efficient Solution is not discussed in the video

#1

The time complexity of the given solution of prime numbers is O(n). Efficient solution has a time complexity O(sqrt(n)). Please explain that solution

#2

@piyushabhiranjan30,

If a number n is not a prime, it can be factored into two factors a and b :

n = a * b

Now a and b can’t be both greater than the square root of n , since then the product a * b would be greater than sqrt(n) * sqrt(n) = n .

So in any factorization of n , at least one of the factors must be smaller than the square root of n , and if we can’t find any factors less than or equal to the square root, n must be a prime.

Hence, to check for prime number we can only check till sqrt(n)