Как можно быстрее всего узнать сколько находится простых чисел до заданного числа (нужно до 48 миллиардов хотя бы)?

Ответить
Ответить
Комментировать
0
Подписаться
0
2 ответа
Поделиться

Количество простых чисел π(х), не превосходящих заданного числа х асимптотически равно:

1) х/ln x - одна из первых оценок, восходящая ещё к Гауссу. Является теоремой. 

2) π(х) = Li x + O(sqrt x * ln^2 (x)). Где Li (x) - интегральный логарифм. Гораздо более точная оценка. Но целиком зависит от справедливости гипотезы Римана. При этом начиная с числа Скьюза π(х) > Li (x). По некоторым оценкам, оно равно 8,185 * 10^370. 

5
-2
Прокомментировать

Если есть возможность написать и скомпилировать программу, то алгоритмов для определения простых чисел довольно много, зачастую они очень хитрые и неочевидные, но найти их несложно 

Наиболее примитивный будет следовать из определения простого числа. Что-то вроде 

<выбираем очередное число>

<последовательно делим на 2, 3 и далее вплоть до половины данного числа, дальше смысла нет>

<как только остаток от деления выходит равным нулю, переход к следующему числу, так как это уже точно не простое>

<если прошли все деления от 2 до половины числа и так и не было нулевого остатка, то вывод этого числа где-то на экране и переход к следующему числу>

Но это хреновый алгоритм, так как очень долгий. Когда-то из интереса написал его на Си и запустил, до 10 миллионов он считал часов так несколько, о 48 миллиардах речь не идёт. 

 Но можно найти более хитрые алгоритмы, основанные на математических критериях простого числа, а реализовать их можно где угодно, думаю, даже в Экселе

3
-4

Да, это был плохой алгоритм. :)

-2
Ответить

Плохой ответ. Больше подходит для девочек.

+2
Ответить

Чем вас так обижали по жизни девочки, что вы им этот алгоритм рекомендуете?) 

-2
Ответить
Ещё 1 комментарий

Не давали, потому что я аутист. Для меня этого достаточно, чтобы считать девочек эквивалентом фекалий.

+2
Ответить
Прокомментировать
Ответить