Probabilistic computing with p-bits is a powerful, unique paradigm alternative to classical computing and holds experimental advantages over certain forms of quantum computing. Stochastic nanodevices have been experimentally demonstrated to act as artificial neurons in solving certain problems through probabilistic computing. Still, many open questions about the breadth and size of soluble problems remain. We demonstrate the capability of probabilistic computing made of a stochastic nanodevice network in solving likely NP (non-deterministic polynomial time)-complete number theory problems associated with combinatorial optimization, which can be implemented using a network of optical parametric oscillators. These simulation results show robustness across all problems tested, with great potential to scale to solve substantially larger problems.