Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C

Teste de primalidade por divisão por tentativa

Verifica se um número inteiro é primo testando possíveis divisores apenas até à sua raiz quadrada. Em C, a condição `d <= n / d` permite verificar esse limite sem risco de transbordo numa multiplicação.

Versão: C23; repository compiler flag, production runtime not attested

Sintaxe

for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }

O teste de primalidade por divisão por tentativa verifica se n tem um divisor diferente de 1 e de n. Primeiro, rejeita n < 2, aceita n == 2 e rejeita todos os outros números pares. Para os restantes candidatos, testa apenas valores ímpares de d, a partir de 3. Se n % d == 0, o número é composto. Se o ciclo não encontrar nenhum divisor, o número é primo.

Os divisores surgem aos pares: se n = a * b e ambos os fatores forem maiores do que 1, pelo menos um deles não ultrapassa a raiz quadrada de n. O limite é inclusivo: para 49, o ciclo também tem de testar 7.

Para verificar o limite dos divisores sem transbordo, usa d <= n / d em vez de d * d <= n. Quando n e d são positivos, a divisão inteira em C arredonda o quociente para baixo, pelo que as duas condições são matematicamente equivalentes. A primeira evita, porém, calcular um produto que poderia ultrapassar o intervalo de valores de int e causar comportamento indefinido. No pior caso, o algoritmo faz O(√n) tentativas e utiliza O(1) de memória adicional.

Exemplos

#include <stdio.h>

static int is_prime(int n)
{
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;

    for (int d = 3; d <= n / d; d += 2) {
        if (n % d == 0) return 0;
    }
    return 1;
}

int main(void)
{
    const int values[] = {-7, 0, 1, 2, 4, 9, 29, 49};
    for (size_t i = 0; i < sizeof values / sizeof values[0]; ++i) {
        printf("%d: %d\n", values[i], is_prime(values[i]));
    }
    return 0;
}

Resultado

-7: 0
0: 0
1: 0
2: 1
4: 0
9: 0
29: 1
49: 0

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes