To compute fft with FFTW algorithms I think that it needs to factorizes the array size in prime factors, but it is an hard problem. which Algorithm uses FFTW to do it?
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.
The problem is not really that hard for reasonable vector sizes. Also, FFT precomputes a plan that already lays out the recursion with all the factors, so that the actual processing call is fast. Plans can be saved too. So even the most naive prime factorisation will do the job.
Apart from that, I think I recall FFTw only supports prime factors up to 13, so a test for divisibility is generally very fast. The remainder that does not have prime factors lower or equal to 13 it uses a generic and slower algorithm without factorisation. All that as far as I recall. Read the documentation if you need the details.