Страница 1 из 1

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

Добавлено: 22 дек 2017, 16:57
Ace_400
Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого содержится минимальное число нулей.

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

Добавлено: 22 дек 2017, 17:27
Romeo
Что именно не получается?

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

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

Добавлено: 26 мар 2018, 01:28
Andrey1302
Я бы тут применил маленькую хитрость. В пакете GMP есть библиотечная функция генерации простых чисел. А посчитать сумму битов можно в цикле без проблем.

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

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

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