Продолжим изучение Ассемблера. В этой статье я покажу, как написать программу для поиска простых чисел на Ассемблер.
Другие статьи на тему Ассемблер:
Напомню, простые числа — это такие, которые делятся только на единицу и на себя. Если у них есть другие делители, то такие числа называются составными. Для поиска простых чисел существует целая куча алгоритмов. Мы воспользуемся одним из них — решетом Эратосфена.
Программа для поиска простых чисел на Ассемблер
В чем суть алгоритма? Он постепенно отфильтровывает все числа за исключением простых. Начиная с числа 2
и заканчивая n
. Число n
задаешь ты. Как только алгоритм натыкается на очередное простое число a
, он пробегает по всему списку до конца (до n
) и вычеркивает из него все числа, которые делятся на a
. Есть наглядная анимированная гифка. Посмотри ее, и сразу поймешь, как работает решето Эратосфена.

Что здесь происходит?
- Начинаем с двойки.
- Смотрим: очередное число
a
помечено как составное? Да — идем на шаг 5. - Если не помечено (не вычеркнуто), значит,
a
— простое. - Пробегаем по всему списку и вычеркиваем все числа, которые делятся на
a
. - Инкрементируем текущее число.
- Повторяем шаги 2–5, пока не достигли
n
.
Каким образом будем бегать по списку и вычеркивать оттуда составные числа? Сначала нам этот список надо создать! Причем в регистры его точно втиснуть не получится. Нам потребуется битовый массив размером n
. По биту на каждое число от 2
до n
(или вполовину меньше, если мы оптимизируем алгоритм так, чтобы он не видел четные числа; это ты можешь сделать в качестве домашнего задания). Соответственно, чем больше n
, до которого ты хочешь найти простое число, тем вместительней должен быть массив.
Все понятно? Давай закодим!
Реализация
Сначала создаем битовый массив и заполняем его нулями. Мы помещаем массив по адресу 0x8000. Этот произвольно выбранный адрес не конфликтует с нашим кодом, не пересекается с ним.
Обрати внимание на квадратные скобки вот в этой строчке: mov [bx], al
. Что они значат? Так мы просим процессор: а скопируй-ка то значение, что хранится в регистре AL
, в ячейку памяти, на которую указывает регистр BX
. И уж точно это не значит, что мы копируем значение регистра AL
в регистр BX
.
Идем дальше. Если очередное число простое, выводим его на экран.
Что тут делаем? Начинаем с двойки (записываем ее AX
). Затем заходим в цикл и помещаем в BX
указатель на ту ячейку битового массива, которая соответствует числу из регистра AX
. Затем смотрим, записан ли там нолик (ты же помнишь, мы сначала инициализировали весь массив нулями). Если там не ноль, а единица, значит, мы на какой-то из предыдущих итераций уже пометили это число как составное. В таком случае прыгаем на @@already_marked
. А если все-таки ноль, вызываем display_number
, чтобы показать найденное простое число.
Обрати внимание на префикс byte
в инструкции cmp
. Он говорит ассемблеру о том, что мы сравниваем байты (8-битные значения), а не слова (16-битные значения).
Здесь, как и в предыдущем куске кода, сначала помещаем в BX
указатель на ту ячейку битового массива, которая соответствует числу из регистра AX
. Но только первоначально выполняем инструкцию add
дважды. Зачем? Нам сейчас нужно не само простое число, а те числа, которые делятся на него.
Перед тем как пометить очередное число как составное, проверяем, чтобы значение регистра BX
не выходило за пределы таблицы: table + table_size
(CoMParsion). Инструкция jnc
говорит процессору: прыгни, если флаг переноса не установлен в единицу (Jump if Not Carry). Ну или если по-русски: прыгни, если левый операнд инструкции cmp
больше правого или равен ему.
Если значение регистра BX
все еще находится в пределах битового массива, записываем единичку в ту ячейку памяти, на которую указывает BX
. Обрати внимание: квадратные скобки в строчке mov byte [bx], 1
означают, что мы записываем единицу по адресу, на который указывает BX
. Мы здесь не присваиваем единицу регистру BX
.
И мы снова используем префикс byte
(на этот раз в инструкции mov
). Тем самым говорим ассемблеру, что присваиваем байт (8 бит), а не слово (16 бит).
Дальше переходим к проверке следующего числа.
Что тут делаем? Если AX
не достиг n
(последнего числа, которое нас интересует), прыгаем на @@next_number
и повторяем там все шаги алгоритма.
Остался последний штрих: добавь в конец программы строчки из библиотеки library.asm
. Вот и всё!
Если ты переписал весь код правильно, то, когда запустишь программу, получишь список простых чисел. Поэкспериментируй с программой. Подставляй разные числа в table_size
, и ты увидишь, как список простых чисел становится короче или длиннее.
И вот тебе еще домашнее задание: измени программу таким образом, чтобы между простыми числами вместо запятых выводились байты 0x0D
и 0x0A
(это значит, что тебе надо будет добавить дополнительный вызов для display_letter
). Посмотри, что произойдет.
Какие бывают режимы адресации
Мы уже много раз использовали конструкцию [bx]
в инструкции mov
, чтобы получить доступ к адресу, который хранится в bx
. В принципе, этого достаточно, чтобы создавать в памяти переменные и пользоваться ими. Ты можешь писать что-то вроде mov [bx], al
/ mov al, [bx]
, и будет тебе счастье.
Но это лишь один из режимов адресации, которые есть у процессора 8088. Когда ты разбираешься, в каких случаях какой режим лучше использовать, ты пишешь более эффективные программы. Вот распространенные режимы адресации, которые можно использовать в mov
и во всех арифметических инструкциях.
Такие конструкции можно писать и в качестве левого операнда, и в качестве правого. Обрати внимание на слагаемые d8
и d16
. d8
— это 8-битное смещение в диапазоне от –128 до 127. d16
— 16-битное смещение в диапазоне от 0 до 65 535.
И в чем же преимущество, когда ты знаешь не один режим адресации ([BX]
), а много? Смотри. Допустим, чтобы прочитать значение из ячейки памяти, где хранится нужный элемент массива, тебе необходимо сложить два регистра. Если ты, кроме [BX],
ничего не знаешь, тебе придется сначала задействовать инструкцию add
и только потом mov
.
Но когда ты знаешь и другие режимы адресации, то, скорее всего, напишешь по-другому, лучше.
Инструкции перехода
До сих пор мы использовали только пять инструкций безусловного и условного перехода: jmp
, je
, jne
, jc
и jnc
. Но процессор 8088 поддерживает намного больше инструкций перехода.
Самое важное, что тебе про них надо помнить, — что у инструкций условного перехода действует ограничение на длину прыжка. Они могут прыгать только на 128 байт назад и только на 127 байт вперед. Но не переживай. Тебе не придется лихорадочно подсчитывать байты своей программы. Если какой-то из условных переходов окажется слишком длинным, nasm сгенерирует дальний прыжок.
Вот список инструкций условного перехода, которые поддерживает 8088.
Большинство из этих инструкций напрямую соотносятся с операторами сравнения в языках высокого уровня.
Кстати, имей в виду, что некоторые инструкции процессора, например mov
, никогда не переключают никакие биты регистра флагов. Это значит, что их можно вставлять между инструкцией сравнения и инструкцией перехода. Например, писать что-то вроде такого.
Что тут делается? Сравниваем AX
с семеркой. Затем помещаем в BX
значение 0x2222
— до того как сделать джамп. Если AX = 7
, загружаем в BX значение 0x7777. Технически этот кусок кода работает медленнее, чем тот, что ниже. Но зато он короче!
Что выбрать, скорость или лаконичность, решай сам.
Итоги
Теперь ты умеешь работать не только с теми переменными, которые хранятся в регистрах, но и с теми, которые хранятся в памяти. Ты знаешь, какие бывают режимы адресации, и понимаешь, как выбирать наиболее подходящий. Плюс ты познакомился с целой кучей инструкций условного перехода. С таким арсеналом ты уже можешь писать на ассемблере довольно-таки мощные программы!