1
Obrigado

Algumas palavras de agradecimento nunca são demais.

Verificar se um número inteiro é um número primo em C

O código a seguir em linguagem de montagem está escrito para arquiteturas x86 (processadores AMD e Intel 32 bits) e usa a sintaxe do Nasm, software livre e gratuito usado em plataformas como Windows e Linux. As funções externas utilizadas foram retiradas da biblioteca C padrão. Desse modo, você não terá problemas para utilizar o código em qualquer computador, pois ele não depende do sistema operacional, somente da arquitetura x86.

Observação: para saber como usar o Nasm para testar esse código, leia o artigo Compilar um programa de linguagem de montagem com o NASM.

Funções para escrever o código

Para escrever esse código, utilizaremos as funções com parâmetros de entrada e valor de saída, as instruções de salto(jmp, jz/je etc.), a aritmética que leva em conta o tipo de variável (com ou sem sinal) e a divisão.

Enunciado

O objetivo é escrever uma função em linguagem de montagem capaz de determinar se um número inteiro sem sinal é primo ou não. Haverá apenas um parâmetro de entrada de tipo inteiro sem sinal que representará o número a ser testado. O valor retornado deve ser 1 se o número for primo e 0 se não for.

Código em C:

int e_primo(unsigned int n); //O modelo dessa função
//Exemplo de uso:
unsigned int nb = 3;
if (e_primo(nb) == 1){
    printf("O número %d é primo!, nb);
}

Você deverá inserir o seguinte código:

extern printf, scanf

seção .data
  inserir db 'Insira um número!', 0xa, 0x0
  sim    db 'C é um número primo', 0xa, 0x0
  não    db 'Não é um número primo', 0xa, 0x0
  format_d db '%d', 0x0

seção .text
  global main

e_primo:
  ;Insira o código aquí!

 
main:
  push ebp
  mov ebp, esp

  ;Deixamos espaço para um número inteiro na pilha
  ;Inseriremos scanf
  sub esp, 4

  ;Frase de boas-vindas
  push inserir
  call printf
  add esp, 4

  ;Solicitamos ao usuário a inserção do número
  push esp ;Endereço do número inteiro
  push format_d ; %d
  call scanf
  add esp, 8

  ;Chamamos a função com o número inteiro inserido
  push dword [esp]
  call e_primo
  ;Testamos o retorno (eax == 0 ?)
  test eax, eax
  ;Se é igual a zero => não é primo
  jz noPrimo
  ;Se não
  push sim
  call printf
  ;Vamos ao final da função para não
  ;inserir na seção noPrimo
  jmp quit

 noPrimo:
  push não
  call printf

 quit:
  leave
  ret

Para lembrar

O que é um número primo

Na matemática, um número primo é um número que só pode ser dividido por 1 ou ele mesmo. Por exemplo, o número 7 é primo pois só é divisível por 1 - como todos os números naturais - e ele mesmo. Já o número 8, por exemplo, não é primo, pois pode ser dividido por 2 e 4, além de 1 e 8.

Com exceção do número 2 (divisível apenas por 1 e 2), todos os outros números primos são ímpares. Isso ocorre pois qualquer número par será divisível por 2, impedindo, portanto, que ele cumpra a regra básica para determinar os números primos.

Tipos de saltos condicionais

Os saltos condicionais não são os mesmos para números com sinal e sem sinal. O mesmo vale para operadores de multiplicação e divisão.

Onde colocar o valor de retorno de uma função

O valor de retorno de uma função deve ser colocado no registro eax.

Código para saber se um número é primo em linguagem de montagem x86

A seguir, veja o código:

e_primo:
  ;Abertura da função
  push ebp
  mov ebp, esp

  ;Carregamos o número n no ecx
  ;ecx será reduzido para testar todos os números
  ;que podem dividir  n de n até 2
  mov ecx, [ebp + 8]
  ;Partimos do princípio que o número é primo (ebx = 1)
  mov ebx, 1
 divisões:
  ;Aqui temos dois casos
  ;Ou inserimos a função e ecx é nosso número
  ;se é menor ou igual a 2, é primo
  ;Ou fazemos a divisão por 2 e, portanto, é inútil continuar
  ;pois não é primo
  cmp ecx, 2
  ;ecx <= 2, o número é primo
  jbe finDivisões
  ;Reduzimos o divisor
  dec ecx
  ;Colocamos em eax o número a dividir (argumento n)
  mov eax, [ebp + 8]
  ;edx deve ser igual a zero 
  xor edx, edx
  ;A divisão (eax/ecx)
  div ecx
  ;O resto da divisão é igual a 0?
  test edx, edx
  ;Se não, o divisor não pode dividir
  ;o número n. Seguimos supondo que ele é primeiro e o dividiremos
  ;por ecx - 1
  jnz divisões
  ;Se o resto é zero significa que o número não é primo
  mov ebx, 0

 finDivisões:
  ;Carregamos o retorno da función com ebx
  ;que contém a resposta
  ;(1: número primo 0: não primo)
  mov eax, ebx
  leave
  ret

Explicação

O algoritmo utilizado nessa dica é bastante simples uma vez traduzido. Veja o que fizemos:

  • Partimos do pressuposto de que nosso número n é primo.
  • Dividimos sucessivamente n por todos os números menores que n até 2 inclusive.
  • Se for divisível por algum deles (ou seja, resto igual a zero), então paramos o teste e concluímos que o número não é primo.
  • Contudo, se o número for menor ou igual a 2, não fazemos nenhum teste e concluímos que ele é primo.

Esquematicamente, essa é a nossa ideia:

Função e_primo (n: inteiro sem sinal): inteiro
    divisor = n
    primo = 1
    Enquanto n <= 2
    Fazer
        divisor = divisor - 1
        resto = n mod divisor
        Se resto == 0
        Então
            primo = 0
            sair
        FimSe
     FimEnquanto
Fim
retornar primo

Para isso, devemos utilizar a instrução div que divide eax por um registro dado como parâmetro. Nesse caso, ecx é nosso divisor e é reduzido em uma unidade a cada teste. É uma divisão para números sem sinal (caso contrário, utilizar idiv). O quociente é posto em eax (número n, aumentado a cada teste) e o resto é posto em edx. Temos que testar unicamente o resto. Essas divisões localizam-se na tag “divisões”.

Esse algoritmo poderia ser otimizado, mas esse não é nosso objetivo. Afinal, nosso interesse aqui não são os números primos, mas a utilizar a linguagem de montagem.

No código, quando escrevemos div ecx, temos como resultado: eax = eax / ecx y edx = eax % ecx. É preciso tomar cuidado para colocar edx com valor 0.

Assim, temos: eax = edx:eax / ecx et edx = edx:eax / ecx.

Com edx com valor 0, garantimos que edx não adiciona bits significativos na divisão.

Foto: © Everypixel

Veja também
Este documento, intitulado 'Verificar se um número inteiro é um número primo em C ', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.

Assine nossa newsletter!

Receba toda semana o melhor conteúdo

Assine nossa newsletter!