Boolean Networks (BN) and Probabilistic Boolean Networks (PBNs) are useful models for genetic regulatory networks, healthcare service systems, manufacturing systems and financial risk. This paper focuses on the construction problem of PBNs. We propose the Division Pre-processing algorithm (DPre), which breaks a non-negative integer matrix P with constant positive column sum into two non-negative integer matrices Q˜ and R˜, each with constant column sum, such that P = dQ˜ + R˜ for some positive integer d. We combine DPre with two existing PBN construction algorithms to form a novel PBN construction algorithm called the Single Division Pre-processed SER2-GER algorithm (SDS2G). Our computational experiments reveal that SDS2G gives significantly better performance compared with other existing PBN construction algorithms, and that SDS2G is fast. Lastly, we derive a new lower bound related to PBN construction, and this new theorem generalizes a lower bound theorem in a previous paper.