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
- Numero primo em c
- Como saber se um numero é primo - Melhores respostas
- Numeros primos em c - Melhores respostas
- Lista duplamente encadeada em c - Dicas -C
- Variaveis c++ - Dicas -C++
- Condicionais em c - Dicas -C
- Falcon c++ - Downloads - Programação
- Fila em c - Dicas -C
Assine nossa newsletter!
