Check if an integer is a prime number in C


#Check #integer #prime #number

The following code in assembly language is written for x86 architectures (AMD and Intel 32-bit processors) and uses the syntax of Nasm, free software used on platforms such as Windows and Linux. The external functions used were taken from the standard C library. This way, you will have no problems using the code on any computer, as it does not depend on the operating system, only on the x86 architecture.

  • Functions for writing code

  • Statement

  • To remember

    • What is a prime number

    • Types of conditional jumps

    • Where to put a function’s return value

  • Code to know if a number is prime in x86 assembly language

  • Explanation

Note: to learn how to use Nasm to test this code, read the article Compile an assembly language program with NASM.

Functions for writing code

To write this code, we will use the functions with input parameters and output value, the jump instructions (jmp, jz / je etc.), the arithmetic that takes into account the type of variable (with or without sign) and the division .

Statement

The goal is to write a assembly language function able to determine if an unsigned integer is cousin or not. There will be only one unsigned integer input parameter that will represent the number to be tested. The returned value must be 1 if the number is prime and 0 if not.

C code:

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);
}

You must enter the following code:

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

To remember

What is a prime number

In mathematics, a prime number is a number that can only be divided by 1 or itself. For example, the number 7 is cousin because it is only divisible by 1 – like all natural numbers – and itself. The number 8, for example, is not prime because it can be divided by 2 and 4, in addition to 1 and 8.

With the exception of the number 2 (divisible by 1 and 2 only), all other prime numbers are odd. This is because any even number will be divisible by 2, thus preventing it from complying with the basic rule for determining prime numbers.

Types of conditional jumps

Conditional jumps are not the same for numbers with sign and no signal. The same goes for multiplication and division operators.

Where to put a function’s return value

The return value of a function must be placed in the eax record.

Code to know if a number is prime in x86 assembly language

Next, see the code:

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

Explanation

O algorithm used this tip is quite simple once translated. See what we did:

  • We assume that our number n is cousin.
  • We successively divide n for all numbers less than n to 2 inclusive.
  • If divisible by any of them (ie remainder equal to zero), then we stop the test and conclude that the number not cousin.
  • However, if the number is less than or equal to 2, we do not do any tests and conclude that it is cousin.

Schematically, this is our idea:

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

For that, we must use the div instruction which divides eax by a record given as a parameter. In this case, ecx it is our divider and is reduced by one unit with each test. It’s a division for numbers no signal (otherwise, use idiv). The quotient is put into eax (number n, increased with each test) and the rest is put in edx. We only have to test the rest. These divisions are located in the “divisions” tag.

This algorithm could be optimized, but this it is not our goal. After all, our interest here is not in prime numbers, but in using assembly language.

In the code, when we write div ecx, we have as a result: eax = eax / ecx y edx = eax% ecx. Care must be taken to place edx with value 0.

Thus, we have: eax = edx: eax / ecx et edx = edx: eax / ecx.

With edx with a value of 0, we guarantee that edx does not add significant bits in the division.

Photo: © Everypixel

Related Posts