Ultra-long-period Cepheids (ULPCs) are important in distance-scale studies due to their potential for determining distance beyond ~100 Mpc. We performed a comprehensive search for ULPCs in M31, a local benchmark to calibrate the distance ladders. We use data from the Palomar Transient Factory (PTF), which has imaged M31 using a 1.2-m telescope equipped with a ~7.26 deg2 field-of-view (FOV) camera, usually with daily sampling, since the beginning of 2010. The large FOV, together with the regular monitoring, enables us to probe ULPCs in the bulge, disk, and even out to the halo of M31. Using a difference imaging analysis technique, we found and characterized 3 promising ULPC candidates based on their luminosities, amplitudes and Fourier parameters. The mean absolute magnitude for these 3 ULPC candidates, calibrated with latest M31 distance, is M_R=-6.47mag. Two out of the 3 ULPC candidates have been reported in literature, however their published periods from Magnier et al. are about half of the periods we found in this work. The third ULPC candidate is a new discovery. We studied 5 other candidates and determined that they are probably Mira-like or ultra-long-period variables, but not ULPCs.