Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по математике

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 763 RSS
←   Сентябрь 2017   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
24.09.2017
03:00:48
14:17:57
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru
Открыта: 14-07-2005

Автор
Калашников О.А.

Статистика

763 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по математике


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Михаил Александров
Статус: 6-й класс
Рейтинг: 1268
∙ повысить рейтинг » 		Лангваген Сергей Евгеньевич
Статус: Академик
Рейтинг: 160
∙ повысить рейтинг » 		Елена Васильевна
Статус: Практикант
Рейтинг: 97
∙ повысить рейтинг »

∙ Математика

Номер выпуска:2109
Дата выхода:27.09.2017, 17:15
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:51 / 63
Вопросов / ответов:1 / 1

Консультация # 191354: Здравствуйте уважаемые эксперты! Занимаюсь переделкой библиотеки численного анализа НИВЦ МГУ и при разборе процедуры вычисления простых чисел типа &quo...

Консультация # 191354:

Здравствуйте уважаемые эксперты!
Занимаюсь переделкой библиотеки численного анализа НИВЦ МГУ и при разборе процедуры вычисления простых чисел типа "решето Эратосфена" столкнулся с одной проблемой вспомогательного характера:
там для вычисления количества простых чисел в диапазоне от 1 до N использует ся формула:

© Цитата:
не больше [ 1.6N / lnN + 1 ] , если N <= 200 ,
или не больше [ N / (lnN-2) + 1 ] , если N > 200.

То, что их количество после вчисления получается действительно "не больше" - та и есть. Однако эта формула при расчёте потребного количества ячеек массива для хранения результата, выдаёт ответ с изрядным завышением. И если такой завышения для диапазона простых чисед от 1 до 100 вполне терпимо, то когда речь идёт о миллионах, миллиардах и т.д., то в этом случае пустых ячеек без результата получается просто бешеное количество.
Сам я программирую расчёт количества так:
Если N <= 200 То
  Количество =  1.6*N / LOG(N) + 1
Иначе
  Количество = N / (LOG(N) - 2) + 1


И у меня вопрос:
- ошибся я;
- ошибка у них там в алгоритме;
- если никто не ошибся, есть ли формулы вычисляющее более "разумное" количество предполагаемых простых чисел?

Дата отправки: 17.09.2017, 17:03
Вопрос задал: Вадим Исаев ака sir Henry (Старший модератор)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Лангваген Сергей Евгеньевич (Академик):

Здравствуйте, Вадим Исаев ака sir Henry!

Лучшие результаты должна давать следующая оценка количества п(x) простых чисел, не превосходящих x:
п(x) ≤ (x/ln x)*(1 + 1.2762/ln x) при x>1.
Эта формула была предложена в статье 1999 года, автор Pierre Dusart.
Согласно энциклопедии, в программе НИВЦ МГУ использовалась более ранняя оценка.

Консультировал: Лангваген Сергей Евгеньевич (Академик)
Дата отправки: 26.09.2017, 20:48

5
нет комментария
-----
Дата оценки: 27.09.2017, 09:12
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное