Factoring keeps being described as a 2^(n/2) problem, yet AFAIK [...], it's doable in linear (O(n)) time. Remember that the 'n' is the length of the input. /* Algorithm: To factor the number n, start with n boxes, each with on "marble." Remove last box, put it's marble in box #1. If all boxes have the same number of marbles, the number is factored. If not, remove last box. Put marble in box #2. Compare. Etc. possible optimizations: div by each prime l for a quicker starting point. (2,3...) */ This algorithm is equivalent to trial division by each number less than n. At each stage the 'box counter' is equal to the remainder and the 'number of boxes' is the divisor. Now since n can be encoded in lg n bits (lg = base 2 logarithm), the length of the input is N = lg n. The representation of the boxes can be represented in O(N) bits; use two counters, each the length of the input. The number of trial divisors is about 2^N, yielding an exponential time algorithm. Eric