Найти все простые числа С++

[vsubotka]

Помогите пожалуйста, нужно написать программу/
Найти все простые числа из заданной последовательности чисел, не превосходящие заданное натуральное число n, двоичная запись которых представляет собой симметричную последовательность нулей и единиц (начинающуюся единицей).
Цифры не должны заноситься в массив.

[Romeo]

Ну более простого способа, чем следующий, я не придумал. Запустить два счётчика: от последнего бита и от первого, двигать счётчики друг на встречу другу и проверять равны ли биты, на которые счётчики указывают. Ну и делать это нужно для каждого числа от 1 до n в цикле.

Если отважишься запрограммировать самостоятельно, я могу расписать чуть детальнее алгритм.

[somewhere]

Тут еще с симметрией непределенность получается. Например, 101 - вроде как симметрична, а 00000101 - уже нет, не смотря на то, что это одно и тоже число

[Romeo]

Нет, в задании написано "начинающуюся единицей". Лидирующие нули мы должны опускать. То есть первый шаг - это найти левую границу откуда начинать сравнивать зеркальность. У меня есть стойкое предчуствие что первый ненулевой бит нашего числа x будет равен "целая часть от log_2 (x)". Всё верно?

[somewhere]

Ну да. На ассемблере я бы сделал так:
Если принять N = log_2 (x), то я бы крутил бы Х вправо, а другое число У , первоначально равное 0 - крутил бы влево через флаг переноса. Через N итераций в Y было бы перевернутое число. В случае зеркального расположения битов Х = У в конце.
На сях вращение - это
У = (Y << 1) + (Х & 1); (синтаксис плохо помню)

[Romeo]

На ассемблемере там основной цикл вообще в десяток команд укладывается. Но, к сожалению, в С++ у нас напрямую не доступен флаг переноса и команды sbb и adc, учитавающие этот регистр.

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

Использую всё тот же интуитивно понятный алгоритмический язык собственного изобретения

Код: Выделить всё

Ввод Число;

СтаршийБит = log_2 (Число);
МаскаСЛевымБитом = (1 << СтаршийБит);
МаскаСПравымБитом = 1;

Пока МаскаСЛевымБитом > МаскаСПравымБитом
{
   Если ((Число & МаскаСЛевымБитом) != 0) != ((Число & МаскаСПравымБитом) != 0) Прервать;
   МаскаСЛевымБитом >> 1;
   МаскаСПравымБитом << 1;
}

Если МаскаСЛевымБитом <= МаскаСПравымБитом
   Вывод "Симметричное";
Иначе
   Вывод "Несимметричное";

[somewhere]

Так можно вообще без циклов обойтись. Если известно, что СтаршийБит = log_2 (Число), то можно отделить две битовые половинки числа и заXORить их друг с другом. Если в результате 0, значит симметрия. Или вот так:

Код: Выделить всё

ДвеЛевыеПоловинки = (Число >> (СтаршийБит >> 1)) + (255 << (СтаршийБит >> 1));
Если ДвеЛевыеПоловинки = Число Тогда
   Вывод "Симметричное";
Иначе
   Вывод "Несимметричное";

Использую всё тот же интуитивно понятный алгоритмический язык собственного изобретения

На 1С похоже

[Romeo]

С XOR не получится, как бы этого не хотелось. Контрпример, число с 1 в начале и 1 в конце и множеством нулей всередине. Скажем 1000001. XORим мы тогда 1000 и 0001, что даёт 1001.

По поводу приведёного алгоритма: я что-то не очень понял, как он должне работать.
Если исходное число, скажем, было 1001, а 255 в бинарном представлении это 8 единичек, то ДвеЛевыеПоловинки = 10 + 1111111100 = 1111111110, что не равно исходному числу.

Без инверсирования числа, либо без битового обхода с двух концов, эту задачу никак не решить, как я понял. Оба варинты по интуитивности равны, а по скорости иверсирование несколько быстее, так как длину числа не нужно вычислять. Но всё равно сложность обоих алгоритмов будет O(N). Линейной сложности никак не добиться.

[somewhere]

Если исходное число, скажем, было 1001

Недописал, потерял мысль)) Вот как я хотел:

ДвеЛевыеПоловинки = (Число >> (СтаршийБит >> 1)) + (Число & (255 << (СтаршийБит >> 1)));

Но тут я забыл, что вторая половинка все равно не развернута. Но все-таки где-то внутри я чувствую что можно без циклов, подумаю на досуге.