Cooley-Tukey FFT: You don't have to zeropad to a power of 2?
Yes.  If you can factor length N, Cooley-Tukey will give you an DFT computation that uses less multiplies than an unfactored DFT.  A power of 2 factorization requires less lines of text or shorter equations to explain.  But any small prime factors allows a straight forward extension to the power-of-2 explanation or proof of the algorithm.

Many newer FFT libraries (iOS Accelerate for one example) allow efficient composite FFT lengths with factors of 2,3,5 and maybe more, thus requiring less padding to get to the next useful composite length.