For number > 10^7 why we are only checking prime numbers from 0 to square root of n prime numbers Please explain

#1

for number > 10^7 why we are only checking prime numbers from 0 to square root of n prime numbers Please explain

#2

Hey @sahazeer123, let us answer your question via, example
And read this example very carefully,
Think of any non-prime number, for example 49 okay, now what are the numbers which divides 49 by gives you remainder 0
They are 1 & 7 which means if you are starting from 1 till sqrt(49) if there is no number then there won’t be any number from sqrt(49) to 49
Now let us Discuss for numbers which are not perfect square and are also not prime. For example 27
Now when you calculate sqrt(27) it will give you 5 so now what you have to do is only check whether is there any number between [1,5] which when divided from 27 gives remainder 0 and you will find 1 & 3 will divide it with remainder 0 moreover elements bigger then sqrt(27) which divide them are 9 so there’s no need to calculate 9 cause you have already founded 3 and you will be saved for doing extra iterations to find numbers cause 9 is (3)^2
Hope it helped you :grinning:
Keep coding :+1:

1 Like
#3

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.