Использовав теорему о распределении простых чисел, получим такую асимптотическую оценку: x/lnx = 48 254 942 - 1 сек. если считать на обычном калькуляторе.
Применим гипотезу об интегральном логарифме. Получим интеграл: int (dx/lnx) в пределах интегрирования от 1 до миллиарда. Он даст такой численный результат: 50 849 235 - 1 сек. Результат гораздо точнее, но имеет свою погрешность. И существенный недостаток: целиком опирается на недоказанную гипотезу Римана. Так что не факт, что эта оценка: 1) всегда будет точна; 2) никогда не станет точно равна количеству простых чисел для любого их числа начиная с какого-то момента.
Точное число простых чисел до миллиарда: 50 847 534. Это тоже своего рода алгоритм: гугление таблицы количества простых чисел до некоторого заданного числа. Если таблица под рукой: требует меньше секунды, пока компьютер ищет. Ясно, что это шутливый алгоритм. Но почему бы и нет? )
Использовав решето Аткина, получим точное число простых чисел за меньшее время в сравнении с некоторыми другими алгоритмами (вроде решета Эратосфена). Данный алгоритм имеет асимптотическую сложность О(x/ln(ln(x)). На входных значениях порядка 10^9 решето Аткина быстрее решета Эратосфена в 9.2 раза. Рассмотрим, сколько времени ему требуется для некоторых значений х:
10 000 000 требует 0.15 сек.
100 000 000 занимает уже 2.16 сек
1 000 000 000 чисел, как заявлено в условии, требует для точного подсчёта уже 48.76 сек. Для сравнения: некоторые реализации решета Эратосфена требуют примерно 10 минут.
Тем самым: применяя интегральный логарифм, мы получим асимптотическую оценку с некоторой погрешностью всего за 1 секунду, а применяя решето Аткина, получим точный результат почти за 49 секунд