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]: 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
Following is an elegant solution to the problem [1]: 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
No comments:
Post a Comment