A number is prime or not

#1

why we have to traverse only upto n/2 to check whether a number is prime or not,should not it be from 2 to n-1

#2

@namangarg31
Actually you can just traverse upto sqroot(N)
The reason is simple
If x * y = N
Now if y > sqroot(N)
Then x must be < sqroot(N)

So if we check all numbers from 2 to sqroot(N) and we can’t find any such x that divides N completely, then there exists no y > sqroot(N) such that x * y = N

#3

Actually you can just traverse upto sqroot(N)
The reason is simple
If x * y = N
Now if y > sqroot(N)
Then x must be < sqroot(N)

So if we check all numbers from 2 to sqroot(N) and we can’t find any such x that divides N completely, then there exists no y > sqroot(N) such that x * y = N

#4

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.