Среди простых чисел, не превосходящих заданного N

Ответить

Код подтверждения
Введите код в точности так, как вы его видите. Регистр символов не имеет значения.

BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[flash] ОТКЛЮЧЕН
[url] ВКЛЮЧЁН
Смайлики ОТКЛЮЧЕНЫ

Обзор темы
[quote=Romeo post_id=102647 time=1522094290 user_id=58] Задача алгоритмическая. Не думаю, что преподаватель примет задачу с использованием внешних библиотек. Так или иначе, человек не отвечал три с половиной месяца. Думаю, он сюда больше не зайдёт :) [/quote]
   

Развернуть Обзор темы:Среди простых чисел, не превосходящих заданного N

Re: Среди простых чисел, не превосходящих заданного N

Romeo »26 мар 2018, 22:58

Задача алгоритмическая. Не думаю, что преподаватель примет задачу с использованием внешних библиотек.

Так или иначе, человек не отвечал три с половиной месяца. Думаю, он сюда больше не зайдёт :)

Re: Среди простых чисел, не превосходящих заданного N

Andrey1302 »26 мар 2018, 01:28

Я бы тут применил маленькую хитрость. В пакете GMP есть библиотечная функция генерации простых чисел. А посчитать сумму битов можно в цикле без проблем.

Re: Среди простых чисел, не превосходящих заданного N

Romeo »22 дек 2017, 17:27

Что именно не получается?

Я бы это делал следующим образом:
1. Отсеиваем простые числа с помощью решета Эратосфена (если есть ограничивающее сверху N, то этот способ будет работать куда быстрее, чем проверка всех множителей, хотя и потребует больше памяти).
2. Обходим простые числа и считаем их битовые единицы (например, наложением маски, хотя есть и более быстрые варианты, но они требуют владение ассемблером).

Среди простых чисел, не превосходящих заданного N

Ace_400 »22 дек 2017, 16:57

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

Вернуться к началу