Prime Factorization

Prime factorization is a relatively simple problem, and occurs as a part of many algorithmic problems in one form or another. However, we often perform a lot of unnecessary computation when trying to solve it, like generating primes, checking for primality, etc.

Following is an elegant solution to the problem [1]:

	prime_factorization(long x)
	{
	long i; /* counter */
	long c; /* remaining product to factor */
	c = x;
	while ((c % 2) == 0) {
	printf("%ld\n",2);
	c = c / 2;
	}
	i = 3;
	while (i <= (sqrt(c)+1)) {
	if ((c % i) == 0) {
	printf("%ld\n",i);
	c = c / i;
	}
	else i = i + 2;
	}
	if (c > 1) printf("%ld\n",c);
	}

view raw prime_factorize.cpp hosted with ❤ by GitHub

The above code prints the prime factors of a number. Each prime is printed as many times as it occurs in the prime factorization of the number. The code can be easily modified to count the no. of prime factors, determine exponent of each prime etc.

Do you see why this works?

[1] - http://www.cs.sunysb.edu/~skiena/392/programs/primes.c