How FFTW factorizes array length?
FFTW factorizes by testing against a table of primes.  This is fast due to the fact that the size of the table is limited because the size of computer memory in which the FFT data is to be computed is itself limited to a very tiny number in mathematical terms (less than a few petabits). You only need up to the square root of that number.