The beam training protocol in millimeter-wave cellular systems requires a long processing time that is proportional to the product of the number of Tx beams, number of Rx beams, and number of neighbor base stations. In this paper, a preamble design technique that can significantly reduce the processing time for beam training in an orthogonal-frequency-division-multiplexing-based cellular system is proposed by transmitting multiple beams with their corresponding Tx beam IDs (BIDs) and cell ID (CID). The Zadoff–Chu (ZC) sequence, with its length given by a multiplication of two prime numbers, is proposed for an efficient CID and BID (CBID) search in a preamble design. It is shown by computer simulation that the proposed preamble design technique can obtain a 10- to 20-fold computational complexity gain in CBID detection and achieve a performance (0.1-dB signal-to-noise ratio shift) that is close to that of a ZC sequence with a prime length.