In this note we present the Prime Number Paradigm: “Nature encodes its laws with the aid of prime numbers.” We claim that prime number skeletons of data-sets contain the basic structures represented them. This paradigm is illustrated by a variety of data: from astrophysics to geophysics (including petroleum data), and reading comprehension. We remark that the ideas about the fundamental (and even mystical) role played by primes in mathematics and in physics were discussed by many scientists during the last 2000 years. The main advantage of our approach is its close connection with real experimental data. To present deeper patterns in data, the prime skeletons can be extended to p-adic skeletons. P-adic numbers play the important role number theory and recently they started to be widely used in theoretical physics, form string theory and theory of complex disordered systems to geophysics.