Prime factorization

#1

why in prime factorization we only checked till sqrt(n)

#2

@tusharkhandelwal315,
Thats not true, for e.g take 12, its SQRT root is 3.461, but 4 is a non prime factor, greater that sqrt(12).

#3

why in prime factorization we only checked till sqrt(n)

#4

@tusharkhandelwal315,
We checked only till sqrt(n) because factors occur in pair, for e.g f1 * f2 = n let without loss of generality say f1 <= f2, thus we can see, obviously, f1 <= sqrt(n). Thus we iterate from 1 to sqrt(n), and for each f1 we find f2 = n/f1. If we want only prime factors, we put a condition, is_prime(f1)==true and is_prime(f2)==true

#5

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.