Hi all,
In this post am going to explain find prime factors in O(sqrt(n)).
Steps
- We will reduce the given no to odd no.
- After which we will start checking for divisibility from 3 to sqrt(N) while increasing our counter by 2 as we can skip checking for even no’s.
- At last we check for special condition when n is itself a prime no.
Well you may ask why till sqrt(N)? Let me explain.
Every composite number has at least one prime factor less than or equal to square root of itself.
Want me to prove it? OK let’s prove it.
Let a and b be two factors of n such that a*b = n.
If both are greater than √n, then a.b > √n, * √n, which contradicts the expression “a * b = n”.
Hence its correct.
# include <stdio.h>
# include <math.h>
void main()
{
int n,s;
scanf("%d",&n);
s=sqrt(n);
// converts n to odd no
while (n%2 == 0)
{
printf("%d ",2);
n /=2;
}
//we can skip one element as n is odd now
for (int i=3;i <= sq;i = i+2)
{
while (n%i ==0)
{
printf("%d ",i);
n /=i;
}
}
// handles condition when n is itself a prime no
if (n > 2)
printf ("%d",n);
}