Prime factorization algorithm: How to make it faster?

Question

I have a program that finds the prime factors of a given number. The algorithm works in the way described below.

1) While n is divisible by 2, print 2 and divide n by 2.

2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.

3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.

Is there a way to make it faster?

Answer 1

You can make it faster by only dividing by primes rather than composites. If it's divisible by a composite, you will have already discovered that when dividing by the prime factors of that composite. For example, there's no point testing to see if a number is divisible by 9 if you've already established it's divisible by 3 (and reduced it correctly).

In addition, I wouldn't advance the test value (by two in your case, to the next prime in mine) until you're sure the value you're testing is non-divisible by it.

Case in point: 27. When your test value is 3, your algorithm divides 27 by 3 to get 9, then immediately increase the test value to 5. It should be left at 3 until the number you're dividing it by is no longer a factor.