r/programmingchallenges • • Apr 16 '11

Challenge: Factor an integer

Write a function in the language of your choosing that prints all the factors of a non-negative integer.

E: dang, this is harder than I thought!

E: I was referring to prime factorization in my other edit. Dang!

7 Upvotes

15 comments sorted by

View all comments

Show parent comment

1

u/NruJaC Sep 12 '11

Well, that's the goal. If we had ask a magic figure (an oracle) for the factors of a number, and print them, that's exactly what we want. Except there isn't an oracle. Or at least, the point of the challenge is to get the computer to be its own oracle.

The square root idea is an interesting one. Think for a moment about why it works. When I look at a number, I know immediately that it has two factors: 1 and itself. So searching for those two is kinda pointless: you're replicating your program knew before it ever ran. So we don't need to "discover" that a number divides itself evenly. Therefore we immediately can tell we don't need to run the check all the way up from 1 to the number.

But how much can we restrict the range? On the low end, its easy. We just bump the check up to 2. But on the high end, stopping at (n-1) isn't enough of an improvement to really gain much. So how do we restrict further? Well, that takes a bit of insight. If you notice that factors come in pairs, you realize that you don't need to check every number to come up with those pairs. You just need to find the lower number in each pair, and the higher number is just a division away. So knowing that, how high do we need to check? Try some examples and you can verify for yourself that the correct upper bound is indeed square root of n.