Оценка кол-ва натуральных множителей для множества натуральных чисел
Доброго времени суток.
Задан миллион натуральных чисел, каждое в диапазоне от 1 до миллиарда.
Как получше оценить кол-во натуральных чисел (не обязательно простых) , которые являются множителем хотя бы одного из заданных?
Интересует только оценка сверху.. .Самый худший случай. Если получится дать оценку хотя бы 10 миллионов, то уже хорошо.
То, что таких множителей может оказаться больше миллиона, следует отсюда:
https://ru.wikipedia.org/wiki/Функция_распределения_простых_чисел
(там табличка есть, в диапазоне 1..миллиард около 50M простых чисел)
На компьютере при случайной выборке получается примерно 6.9 мил. натуральных делителей, 422 тыс. простых делителей.
В Вашей ссылке есть формула :
Pi(x) =
Li(x) + O(sqrt(x)*lnx)
Pi(x) – кол. простых
Лог. интегральный : Li(1000000000.) = 50849234.96
nops(select(isprime,[$1..100000])) = 9592 (число простых до
100000 тыс)
(про=сто так … точное колисчество простых …дальше комп не
стал грузить :)))