The problem of packing a system of particles as densely as possible is foundational in the field of discrete geometry and is a powerful model in the material and biological sciences. As packing problems retreat from the reach of solution by analytic constructions, the importance of an efficient numerical method for conducting de novo (from-scratch) searches for dense packings becomes crucial. In this paper, we use the divide and concur framework to develop a general search method for the solution of periodic constraint problems, and we apply it to the discovery of dense periodic packings. An important feature of the method is the integration of the unit-cell parameters with the other packing variables in the definition of the configuration space. The method we present led to previously reported improvements in the densest-known tetrahedron packing. Here, we use the method to reproduce the densest-known lattice sphere packings and the best-known lattice kissing arrangements in up to 14 and 11 dimensions, respectively, providing numerical evidence for their optimality. For nonspherical particles, we report a dense packing of regular four-dimensional simplices with density ϕ=128/219≈0.5845 and with a similar structure to the densest-known tetrahedron packing.