Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C

Test di primalità per divisioni successive

Verifica se un intero è primo provando i possibili divisori solo fino alla sua radice quadrata. In C, la condizione `d <= n / d` controlla questo limite senza il rischio di overflow dovuto alla moltiplicazione.

Versione: C23; repository compiler flag, production runtime not attested

Sintassi

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

Il test di primalità per divisioni successive verifica se n ha un divisore diverso da 1 e da n. Prima scarta n < 2, accetta n == 2 e scarta tutti gli altri numeri pari. Per i candidati rimasti, prova solo valori dispari di d, a partire da 3. Se n % d == 0, il numero è composto. Se il ciclo non trova alcun divisore, il numero è primo.

I divisori si presentano a coppie: se n = a * b ed entrambi i fattori sono maggiori di 1, almeno uno non supera la radice quadrata di n. Il limite è incluso: per 49, il ciclo deve provare anche 7.

Per controllare il limite dei divisori senza overflow, usa d <= n / d al posto di d * d <= n. Se n e d sono positivi, la divisione intera in C arrotonda il quoziente verso il basso, quindi le due condizioni sono matematicamente equivalenti. La prima evita però di calcolare un prodotto che potrebbe superare l’intervallo dei valori di int e causare un comportamento indefinito. Nel caso peggiore, l’algoritmo esegue O(√n) tentativi e usa O(1) di spazio aggiuntivo.

Esempi

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

Risultato

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

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti