Так вот — доля простых, конечно, стремится к 0. Но делает это очень медленно. Как 1/ln n. А натуральный логарифм, с точностью до постоянного множителя в ln 10 ≈ 2.30..., это практически количество цифр в записи числа. Так что, если мы возьмём числа от 1 до 10^{42} — нет, давайте его напишем полностью,
1.000.000.000.000.000.000.000.000.000.000.000.000.000.000,
так вот, в этом интервале простое число примерно каждое сотое (и это с учётом того, что половина из чисел чётная, а из нечётных треть делится на 3!).
Так что число простых уменьшается медленно-медленно, и если достаточное число раз "потыкать" — и, что очень важно, уметь достаточно быстро проверять получающиеся числа на простоту! — то при разумном количестве попыток (в сравнении с количеством цифр) на простое число практически "нельзя не наткнуться".

Собственно, без этого бы не работало шифрование RSA — для него нужно придумать два больших простых числа, причём надо, чтобы их произведение не смог разложить на множители атакующий, располагающий большой вычислительной мощностью. Так что из разумного размера таблиц простых (допустим на секунду, что простых чисел оказалось бы значительно меньше) p и q брать было бы нельзя: атакующий просто взял бы эти же таблицы и перебрал варианты пар чисел в них. А так — можно "потыкать-потыкать в случайные числа нужного размера, пока не наткнёшься на простое".

И кстати — давайте я порекламирую ролик Numberphile про герб Trinity Hall (кстати — это не Trinity College, у Тринити Холла на две сотни лет истории больше!). Там в качестве подарка один из выпускников, J. F. McKee, нашёл простое число, рисующее герб Trinity Hall псевдографикой!
(Кстати, в этом же ролике ещё и совершенно прекрасный Тадаси Токиеда (Tadashi Tokieda), но это уже тема для отдельного рассказа!)