Простая программа на ассемблере x86: Решето Эратосфена

  • Tutorial

Вступительное слово


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

И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства x86, с разбора которой можно начать свой путь в покорение низин уровней абстракции.

До ее написания я сформулировал такие требования к будущей программе:
  • Моя программа не должна быть программой под DOS. Слишком много примеров ориентировано на нее в связи с простым API. Моя программа обязательно должна была запускаться на современных ОС.
  • Программа должна использовать кучу – получать в свое распоряжение динамически распределяемую память.
  • Чтобы не быть слишком сложной, программа должна работать с целыми беззнаковыми числами без использования переносов.

Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.

Код я писал с упором больше на стиль и понятность, чем на скорость его выполнения. К примеру, обнуление регистра я проводил не с помощью xor eax, eax, а с помощью mov eax, 0 в связи с более подходящей семантикой инструкции. Я решил, что поскольку программа преследует исключительно учебные цели, можно распоясаться и заниматься погоней за стилем кода в ассемблере.

Итак, посмотрим, что получилось.

С чего начать?


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

Так же встает вопрос, каким образом на таком низком уровне реализуется обмен данными между внутренним миром программы и внешней средой. Тут на сцену выходит API операционной системы. В DOS, как уже было упомянуто, интерфейс был достаточно простой. К примеру, программа «Hello, world» выглядела так:

SECTION .text
    org 0x100

    mov ah, 0x9
    mov dx, hello
    int 0x21
    
    mov ax, 0x4c00
    int 0x21

SECTION .data
    hello: db "Hello, world!", 0xD, 0xA, '$'


В Windows же для этих целей используется Win32 API, соответственно, программа должна использовать методы соответствующих библиотек:

%include "win32n.inc"

extern MessageBoxA
import MessageBoxA user32.dll
extern ExitProcess
import ExitProcess kernel32.dll

SECTION code use32 class=code
    ..start:

    push UINT MB_OK
    push LPCTSTR window_title
    push LPCTSTR banner
    push HWND NULL
    call [MessageBoxA]

    push UINT NULL
    call [ExitProcess]

SECTION data use32 class=data
    banner: db "Hello, world!", 0xD, 0xA, 0
    window_title: db "Hello", 0


Здесь используется файл win32n.inc, где определены макросы, сокращающие код для работы с Win32 API.

Я решил не использовать напрямую API ОС и выбрал путь использования функций из библиотеки Си. Так же это открыло возможность компиляции программы в Linux (и, скорее всего, в других ОС) – не слишком большое и нужное этой программе достижение, но приятное достижение.

Вызов подпрограмм


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

Подпрограммы представляют собой метку, по которой располагается код. Заканчивается подпрограмма инструкцией ret. К примеру, вот такая подпрограмма в DOS выводит в консоль строку «Hello, world»:

print_hello:
    mov ah, 0x9
    mov dx, hello
    int 0x21
    ret


Для ее вызова нужно было бы использовать инструкцию call:

call print_hello


Для себя я решил передавать аргументы подпрограммам через регистры и указывать в комментариях, в каких регистрах какие аргументы должны быть, но в языках высокого уровня аргументы передаются через стек. К примеру, вот так вызывается функция printf из библиотеки Си:

push hello
call _printf
add esp, 4


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

При входе в подпрограмму необходимо создать новый стековый кадр. Делается это следующим образом:

print_hello:
    push ebp ;сохраняем указатель начала стекового кадра на стеке
    mov ebp, esp ;теперь началом кадра является вершина предыдущего


Соответственно, перед выходом нужно восстановить прежнее состояние стека:

    mov esp, ebp
    pop ebp
    ret


Для локальных переменных так же используется стек, на котором после создания нового кадра выделяется нужное количество байт:

print_hello:
    push ebp
    mov ebp, esp
    sub esp, 8 ;опускаем указатель вершины стека на 8 байт, чтобы выделить память


Так же архитектура x86 предоставляет специальные инструкции, с помощью которых можно более лаконично реализовать эти действия:

print_hello:
    enter 8, 0 ;создать новый кадр, выделить 8 байт для локальных переменных

    leave ;восстановить стек
    ret


Второй параметр инструкции enter – уровень вложенности подпрограммы. Он нужен для линковки с языками высокого уровня, поддерживающими такую методику организации подпрограмм. В нашем случае это значение можно оставить нулевым.

Непосредственно программа


Проект содержит такие файлы:
  • main.asm – главный файл,
  • functions.asm – подпрограммы,
  • string_constants.asm – определения строковых констант,
  • Makefile – сценарий сборки

Рассмотрим код основного файла:

main.asm
%define SUCCESS 0
%define MIN_MAX_NUMBER 3
%define MAX_MAX_NUMBER 4294967294

global _main
extern _printf
extern _scanf
extern _malloc
extern _free

SECTION .text
_main:
	enter 0, 0
	
	;ввод максимального числа
	call input_max_number
	cmp edx, SUCCESS
	jne .custom_exit
	mov [max_number], eax
	
	;выделяем память для массива флагов
	mov eax, [max_number]
	call allocate_flags_memory
	cmp edx, SUCCESS
	jne .custom_exit
	mov [primes_pointer], eax
	
	;отсеять составные числа
	mov eax, [primes_pointer]
	mov ebx, [max_number]
	call find_primes_with_eratosthenes_sieve
	
	;вывести числа
	mov eax, [primes_pointer]
	mov ebx, [max_number]
	call print_primes
	
	;освободить память от массива флагов
	mov eax, [primes_pointer]
	call free_flags_memory
	
	;выход
	.success:
		push str_exit_success
		call _printf
		jmp .return
			
	.custom_exit:
		push edx
		call _printf
		
	.return:
		mov eax, SUCCESS
		leave
		ret
	
	%include "functions.asm"

SECTION .data
	max_number: dd 0
	primes_pointer: dd 0
	
	%include "string_constants.asm"


Видно, что программа поделена по смыслу на 5 блоков, оформленных в виде подпрограмм:
  1. input_max_number — с помощью консоли запрашивает у пользователя максимальное число, до которого производится поиск простых; во избежание ошибок значение ограничено константами MIN_MAX_NUMBER и MAX_MAX_NUMBER
  2. allocate_flags_memory — запросить у ОС выделение памяти для массива пометок чисел (простое/составное) в куче; в случае успеха возвращает указатель на выделенную память через регистр eax
  3. find_primes_with_eratosthenes_sieve — отсеять составные числа с помощью классического решета Эратосфена;
  4. print_primes — вывести в консоль список простых чисел;
  5. free_flags_memory — освободить память, выделенную для флагов

Для функций было условлено такое правило: значение возвращается через регистр eax, регистр edx содержит статус. В случае успеха он содержит значение SUCCESS, то есть, 0, в случае неудачи — адрес строки с сообщением об ошибке, которое будет выведено пользователю.

Файл string_constants.asm содержит определение строковых переменных, значения которых, как намекает название файла, менять не предполагается. Только ради этих переменных было сделано исключение к правилу «не использовать глобальные переменные». Я так и не нашел более удобного способа доставлять строковые константы функциям ввода-вывода – подумывал даже записывать на стек непосредственно перед вызовами функций, но решил, что эта идея куда хуже идеи с глобальными переменными.

string_constants.asm
;подписи ввода-вывода, форматы
str_max_number_label: db "Max number (>=3): ", 0
str_max_number_input_format: db "%u", 0
str_max_number_output_format: db "Using max number %u", 0xD, 0xA, 0

str_print_primes_label: db "Primes:", 0xD, 0xA, 0
str_prime: db "%u", 0x9, 0
str_cr_lf: db 0xD, 0xA, 0
	
;сообщения выхода
str_exit_success: db "Success!", 0xD, 0xA, 0
str_error_max_num_too_little: db "Max number is too little!", 0xD, 0xA, 0
str_error_max_num_too_big: db "Max number is too big!", 0xD, 0xA, 0
str_error_malloc_failed: db "Can't allocate memory!", 0xD, 0xA, 0


Для сборки применяется такой сценарий:

Makefile
ifdef SystemRoot
   format = win32
   rm = del
   ext = .exe
else
   format = elf
   rm = rm -f
   ext = 
endif

all: primes.o
	gcc primes.o -o primes$(ext)
	$(rm) primes.o

primes.o:
	nasm -f $(format) main.asm -o primes.o



Подпрограммы (функции)


input_max_number

Код подпрограммы
; Ввести максимальное число
; Результат: EAX - максимальное число
input_max_number:	
	;создать стек-фрейм,
	;4 байта для локальных переменных
	enter 4, 1

	;показываем подпись
	push str_max_number_label ;см. string_constants.asm
	call _printf
	add esp, 4

	;вызываем scanf
	mov eax, ebp
	sub eax, 4
	
	push eax
	push str_max_number_input_format ;см. string_constants.asm
	call _scanf
	add esp, 8
	
	mov eax, [ebp-4]

	;проверка
	cmp eax, MIN_MAX_NUMBER
	jb .number_too_little
	cmp eax, MAX_MAX_NUMBER
	ja .number_too_big
	jmp .success

	;выход
	.number_too_little:
		mov edx, str_error_max_num_too_little ;см. string_constants.asm
		jmp .return	
		
	.number_too_big:
		mov edx, str_error_max_num_too_big ;см. string_constants.asm
		jmp .return	

	.success:
		push eax
		push str_max_number_output_format ;см. string_constants.asm
		call _printf
		add esp, 4
		pop eax
		mov edx, SUCCESS
	
	.return:
		leave
		ret


Подпрограмма призвана ввести в программу максимальное число, до которого будет производиться поиск простых. Ключевым моментов тут является вызов функции scanf из библиотеки Си:

        mov eax, ebp
        sub eax, 4
	
        push eax
        push str_max_number_input_format ;см. string_constants.asm
        call _scanf
        add esp, 8
	
        mov eax, [ebp-4]

Таким образом, сначала в eax записывается адрес памяти на 4 байта ниже указателя базы стека. Это память, выделенная для локальных нужд подпрограммы. Указатель на эту память передается функции scanf как цель для записи данных, введенных с клавиатуры.

После вызова функции, в eax из памяти перемещается введенное значение.

allocate_flags_memory и free_flags_memory

Код подпрограмм
; Выделить память для массива флагов
; Аргумент: EAX - максимальное число
; Результат: EAX - указатель на память
allocate_flags_memory:
	enter 8, 1

	;выделить EAX+1 байт
	inc eax
	mov [ebp-4], eax
	
	push eax
	call _malloc
	add esp, 4
	
	;проверка
	cmp eax, 0
	je .fail
	mov [ebp-8], eax
	
	;инициализация
	mov byte [eax], 0
	
	cld
	mov edi, eax
	inc edi
	mov edx, [ebp-4]
	add edx, eax
	
	mov al, 1
	.write_true:
		stosb
		cmp edi, edx
		jb .write_true
	
	;выход
	mov eax, [ebp-8]
	jmp .success
	
	.fail:
		mov edx, str_error_malloc_failed ;см. string_constants.asm
		jmp .return
	
	.success:
		mov edx, SUCCESS
			
	.return:
		leave
		ret

; Освободить память от массива флагов
; Аргумент: EAX - указатель на память
free_flags_memory:
	enter 0, 1
	
	push eax
	call _free
	add esp, 4
	
	leave
	ret


Ключевыми местами этих подпрограмм являются вызовы функций malloc и free из библиотеки Си.

malloc в случае удачи возвращает через регистр eax адрес выделенной памяти, в случае неудачи этот регистр содержит 0. Это самое узкое место программы касательно максимального числа. 32 бит вполне достаточно для поиска простых чисел до 4 294 967 295, но выделить разом столько памяти не получится.

find_primes_with_eratosthenes_sieve

Код подпрограммы
;Найти простые числа с помощью решета Эратосфена
;Аргументы: EAX - указатель на массив флагов, EBX - максимальное число	
find_primes_with_eratosthenes_sieve:
	enter 8, 1
	mov [ebp-4], eax
		
	add eax, ebx
	inc eax
	mov [ebp-8], eax
	
	;вычеркиваем составные числа
	cld
	mov edx, 2 ;p = 2
	mov ecx, 2 ;множитель с = 2
	.strike_out_cycle:
		;x = c*p
		mov eax, edx
		push edx
		mul ecx
		pop edx
		
		cmp eax, ebx
		jbe .strike_out_number
		jmp .increase_p
		
		.strike_out_number:
			mov edi, [ebp-4]
			add edi, eax
			mov byte [edi], 0
			inc ecx ;c = c + 1
			jmp .strike_out_cycle
			
		.increase_p:
			mov esi, [ebp-4]
			add esi, edx
			inc esi
			
			mov ecx, edx
			inc ecx
			.check_current_number:
				mov eax, ecx
				mul eax
				cmp eax, ebx
				ja .return
			
				lodsb
				inc ecx
				cmp al, 0
				jne .new_p_found
				jmp .check_current_number
			
				.new_p_found:
					mov edx, ecx
					dec edx
					mov ecx, 2
					jmp .strike_out_cycle			
	
	.return:
		leave
		ret



Подпрограмма реализует классический алгоритм для вычеркивания составных чисел, решето Эратосфена, на языке ассемблера x86. Приятна тем, что не использует вызовы внешних функций и не требует обработки ошибок :)

print_primes

Код подпрограммы
; Вывести простые числа
; Параметры: EAX - указатель на массив флагов, EBX - максимальное число
print_primes:
	enter 12, 1
	mov [ebp-4], eax
	mov [ebp-8], ebx
	
	push str_print_primes_label
	call _printf
	add esp, 4
	
	cld
	mov esi, [ebp-4]
	mov edx, esi
	add edx, [ebp-8]
	inc edx
	
	mov [ebp-12], edx
	mov ecx, 0
	.print_cycle:
		lodsb
		cmp al, 0
		jne .print
		jmp .check_finish
		.print:
			push esi
			push ecx
			push str_prime ;см. string_constants.asm
			call _printf
			add esp, 4
			pop ecx
			pop esi
			mov edx, [ebp-12]
		.check_finish:
			inc ecx
			cmp esi, edx
			jb .print_cycle
			
	push str_cr_lf
	call _printf
	add esp, 4
			
	leave
	ret


Подпрограмма выводит в консоль простые числа. Ключевым моментом тут является вызов функции printf из библиотеки Си.

Заключение


Что ж, программа отвечает всем сформулированным требованиям и, кажется, проста для понимания. Хочется надеяться, кому-нибудь ее разбор поможет вникнуть в программирование на низком уровне и он получит от него такое же удовольствие, какое получил я.

Так же привожу полные исходники программы.

Могу так же привести интересный факт. Поскольку с детства нас учили, что программы на языке ассемблера выполняются быстрее, я решил сравнить скорость выполнения этой программы со скоростью программы на C++, которую я писал когда-то и которая искала простые числа с помощью Решета Аткина. Программа на С++, скомпилированная в Visual Studio с /O2 выполняла поиск до числа 230 примерно за 25 секунд на моей машине. Программа же на ассемблере показала 15 секунд с Решетом Эратосфена.

Это, конечно, скорее байка, чем научный факт, поскольку не было серьезного тестирования не было выяснения причин, но как интересный факт для завершения статьи подойдет, как мне кажется.

Полезные ссылки


  1. Список ресурсов для изучения ассемблера
  2. Организация памяти
  3. Решето Эратосфена
  4. Решето Аткина
  5. Стек
  6. Стековый кадр
Поделиться публикацией

Похожие публикации

Комментарии 25

    +3
    > которую я писал когда-то и которая искала простые числа с помощью Решета Аткина.

    Сделайте честное сравнение с одинаковыми алгоритмами.
      0
      32 бит вполне достаточно для поиска простых чисел до 4 294 967 295


      Вообще то должно быть достаточно до 32 млрд, в каждом байте 8 бит.

      А вообще я начинал программирование с этой задачи. Давно, под дос ещё.
        0
        Я не очень понял, можно поподробнее?

        Я имел в виду максимальное беззнаковое число, которое можно представить 4 байтами. Самое большое число в этой программе — максимальное число, ограничивающее поиск, поэтому я и написал про 4 294 967 295.
          0
          Я понял, что это 32 бита на указатель, это 4гб памяти, а поскольку на флаг вычеркивания вы используете 1 байт, то таким образом можно вычислить простые числа до 4млрд. А вообще то на флаг можно использовать 1 бит, кроме того не нужно проверять четные числа, так что требования к памяти для решета можно было бы снизить в 16 раз.
            0
            Действительно, можно исключить четные числа, ноль и использовать по 1 биту на флаг. Но это сделало бы программу несколько менее понятной, так что я отказался от этой идеи. Все-таки это учебный пример, в котором должно быть легко разобраться.

            По поводу выделения 4Гб — мне кажется, столько выделить не получится. Все будет зависеть от того, сколько памяти в распоряжении у ОС в момент выделения.
              0
              Поскольку используется явно 32-битное окружение, выделить (под win32) получится чуть менее 2гб. Если все затеяно в кач-ве обучения — можно попробовать и 64битные режимы, там с памятью ограничения другие )
          0
          32бит а не 32байт. внимательнее читайте ;)
          0
          Возможно, в следующий раз я займусь этим. Интересная задача.
          +1
          Я как-то разбирался с FAIM — ICQ клиент, написанный на asm + WinAPI. Автор маньяк! К сожалению, проект заброшен уже лет пять как.
            +3
            На самом деле с гольным винапи (в том числе для gui) работать на ассемблере не много сложнее, чем на чистом си, например. Тем более, если использовать всякие аналоги invoke для masm и прочие. А протоколы на asm реализовывать вообще сказка. В универе я немалую часть задач на asm кодил, очень уж я тогда его любил. В том числе писал всякие 3D моделирования, матрицы, преобразования, гуро и фонги, полсотни gui-контролов и окошечек, сопроцессорные оптимизации, вот уж проектик был. Недавно только смотрел, слезу аж пустил. Щас мне бы влом такое было делать в 21 веке)
              0
              Друг от нечего делать накодил на асме аналог MediaPlayerClassic. Мало того что размером 40 кбайт (оригинал под 5 метров), так еще и летает как птичка на допотопных машинах.
            +12
            Даёшь больше тёплого лампового асма и меньшая javascript и HTML5 в качестве приложений для десткопа!
              0
              > Для себя я решил передавать аргументы подпрограммам через регистры и указывать в комментариях

              fastcall же!
                0
                В принципе, как-то так и получается: fastcall предполагает передачу аргументов через регистры.
                +2
                Если честно, результаты в 15-25 секунд не впечатляют.

                В этом топике Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение решалась похожая задача, и лучшие времена были порядка 0.04s — 1s. Прямолинейное решение «в лоб» работало порядка 8.5 секунд, что говорит о том, что улучшение алгоритма приводило к ускорению в 10-300 раз. Не уверен, что на ассемблере легко доступна подобная алгоритмическая оптимизация.

                В комментариях отписывались, что 4-х поточный Аткинс работал примерно столько же, сколько и простейший однопоточный Эратосфен. Так что сравнение с 25s на C++ (с возможно менее удачным алгоритмом) вряд ли корректно.
                  0
                  Да тут и не было цели реализовать оптимальный по скорости алгоритм. Так что я не претендовал на то, чтобы впечатлить всех временем выполнения.

                  Но сравнение алгоритмов интересное. Вроде бы, Аткинс должен быть быстрее Эратосфена. Может быть, все дело в реализации? Например, реализация алгоритма работы на первом месте очень оригинальная:

                  //@shadeware
                  #include <cstdio>
                  #include <vector>
                  #include <cmath>
                  unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0"
                  "5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llu\n",A);} 
                  
                    0
                    Подобная «каша» — следствие жёсткого ограничения на размер исходников. Автор делится идеей, и более красивыми исходниками: идея, «красивый код»

                    Кстати, зачем писать на asm, если не задаваться целью написать быстрый код?
                      +1
                      Ясное дело, что все из-за ограничения на размер исходников.

                      Лично я пишу на ассемблере, потому что это интересно само по себе, дает представление о том, как процессор выполняет код и дает отличное представление об организации памяти. Так же можно упомянуть низкоуровневую отладку. Без ассемблера вряд ли получится все это освоить.

                      А если бы мне нужен был быстрый код, я писал бы на C/C++ и компилировал с оптимизациями )
                        +2
                        >>Кстати, зачем писать на asm, если не задаваться целью написать быстрый код?

                        В последнее время компиляторы умнее разработчиков в программах сложнее сложения двух чисел. После оптимизаций код в большинстве случаев получится более производительным, чем при ручном написании на asm.
                        Отдельно можно рассмотреть ситуации типа «истории одного байта» или всяких 1k demo, когда все силы брошены на минимальный размер. Тогда да — asm наше все.

                        Мне вот нравится писать на асме just for fun: начиная с bios/dos программок, и заканчивая GUI софтом типа графического редактора, специфичных обработчиков файлов, да и драйвер с криптографией для win приходилось писать. На более высокоуровневых ЯП это все заняло бы сильно меньше времени, но это банально не интересно :)
                          –1
                          Абсолютно не согласен, с тем что компиляторы умнее разработчиков — я как-то писал код изобилущий коммандами битового сдвига, если это писать на си++, а потом взглянуть на дизасембли — то выйдет совершенно невнятная простынь кода, как ни странно на асме получилось короче, напрмер по той причние что компиляторы С/С++ категорически не хотят задейсвовать операции циклического битового сдвига, а на результат линейного сдвига расходуют целый регистр.
                            +1
                            Короче не значит быстрее.

                            Вот некоторым атомам вообще нужно в коротких функциях перед ret поставить пару nop и в результате будет быстрее.
                              +2
                              код в большинстве случаев получится

                              Да, компиляторы иногда тупят. Речь не о небольших частных случаях, а о ситуации в целом — межпроцедурный и межмодульный анализы они выполняют лучше, подчас отлично додумывая за разработчика, подсовывая векторые инструкции, выполняя встраивание (inline) и т.п.
                        +2
                        Современные C++ компиляторы пишут код лучше 95% программистов на ассемблере, при условии правильного C++ кода :-)
                          0
                          А что на правах организатора известного соревнования по простым числам можете сказать по поводу сравнения алгоритмов Аткинса и Эратосфена? )
                            +1
                            Я могу сказать, что скорость их отличается в разы в лучшем случае, и сильно зависит от реализации => различные трюки и оптимизации позволяют выйти победителем на любом из них.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое