[Tutorials] Finding Prime Factors in O(sqrt(n))

Hi all,

In this post am going to explain find prime factors in O(sqrt(n)).

Steps

  1. We will reduce the given no to odd no.
  2. 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.
  3. 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);

}

2 Likes

won’t improve the asymtotic order, but the the constant factor: get rid of the sqrt()- function in the loop. The runtime of the algorithm will be dominated by calls to sqrt.

1 Like

Ok. Made changes. @ceilks

Good. Carry on.

1 Like