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

Модераторы: Romeo, Hawk, Absurd, WinMain, DeeJayC

Ответить
Ace_400
Сообщения: 1
Зарегистрирован: 22 дек 2017, 16:45

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

Сообщение Ace_400 » 22 дек 2017, 16:57

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

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

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

Сообщение Romeo » 22 дек 2017, 17:27

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

Я бы это делал следующим образом:
1. Отсеиваем простые числа с помощью решета Эратосфена (если есть ограничивающее сверху N, то этот способ будет работать куда быстрее, чем проверка всех множителей, хотя и потребует больше памяти).
2. Обходим простые числа и считаем их битовые единицы (например, наложением маски, хотя есть и более быстрые варианты, но они требуют владение ассемблером).
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Andrey1302
Сообщения: 3
Зарегистрирован: 26 мар 2018, 01:17

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

Сообщение Andrey1302 » 26 мар 2018, 01:28

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

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

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

Сообщение Romeo » 26 мар 2018, 22:58

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

Так или иначе, человек не отвечал три с половиной месяца. Думаю, он сюда больше не зайдёт :)
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Ответить