Numero primo in C

In questa lezione realizziamo un programma che controlli se un numero è primo in lunguaggio C.

Definizione di numero primo

Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori distinti: 1 e se stesso. I numeri primi costituiscono una sequenza fondamentale nella teoria dei numeri e hanno una vasta gamma di applicazioni in vari campi della matematica e della scienza. Ad esempio, vengono utilizzati nell’informatica crittografica per la creazione di algoritmi di crittografia sicura.

La sequenza dei numeri primi comincia con il numero 2, seguito da 3, 5, 7, 11, 13, 17, 19, 23 e così via. Questi numeri sono particolarmente interessanti perché non possono essere suddivisi in fattori più piccoli se non per 1 e loro stessi, il che li rende fondamentali per molte applicazioni matematiche e computazionali.

Algoritmo numero primo in C

Per realizzare un algoritmo che verifica se un numero è primo in linguaggio C, utilizziamo le strutture cicliche. Nell’algoritmo proposto, interrompiamo il ciclo di divisione non appena troviamo due divisori distinti. Questo perché se troviamo un terzo divisore, significa che il numero non può essere primo secondo la definizione, essendo divisibile per un numero diverso da 1 e sé stesso.

Ecco il codice implementato in C per realizzare questa verifica:

#include <stdio.h>

int main() {
    int numero, divisore = 2; // Iniziamo la divisione dal numero 2
    int contaDivisori = 0; // Contatore dei divisori

    printf("Inserisci un numero intero positivo: ");
    scanf("%d", &numero);
    
    // Iteriamo finché il divisore è minore o uguale alla metà del numero e abbiamo al massimo 2 divisori
    while (divisore <= numero / 2 && contaDivisori < 2) {
        if (numero % divisore == 0) // Se il numero è divisibile per il divisore, incrementiamo il contatore dei divisori
            contaDivisori++;
        divisore++;
    }

    // Se il numero ha esattamente un divisore, è primo
    if (contaDivisori == 1)
        printf("Il numero %d è primo.\n", numero);
    else
        printf("Il numero %d non è primo.\n", numero);

    return 0;
}

In questo programma, abbiamo incluso istruzioni chiare per l’utente, invitandolo a inserire un numero intero positivo. L’algoritmo procede quindi a controllare se il numero è primo, utilizzando una serie di operazioni di divisione e confronti per determinare il numero di divisori. Il risultato viene quindi stampato a schermo, indicando se il numero inserito è primo o meno.

Ottimizzazione dell’algoritmo per determinare se un numero è primo in C

Possiamo ottimizzare il programma in diversi modi per renderlo più efficiente. Ecco alcune possibili ottimizzazioni:

Limite superiore della divisione: Piuttosto che dividere fino alla metà del numero, possiamo fermarci alla radice quadrata del numero. Questo perché se un numero ha un divisore maggiore della sua radice quadrata, allora deve necessariamente avere anche un divisore più piccolo, e viceversa. Quindi possiamo risparmiare alcune operazioni di divisione riducendo il limite superiore della divisione.
Controllo della primalità solo per numeri dispari: Osserviamo che tutti i numeri pari maggiori di 2 non sono primi, poiché sono divisibili per 2. Quindi possiamo controllare la primalità solo per numeri dispari, partendo da 3 e incrementando di 2 ad ogni iterazione.
Uscita anticipata dal ciclo: Possiamo interrompere il ciclo non appena troviamo un divisore, anziché contare tutti i divisori fino alla fine. Questo ci permette di risparmiare tempo e operazioni.

Ecco una versione ottimizzata del programma che tiene conto di queste considerazioni:

#include <stdio.h>
#include <math.h>

int main() {
    int numero;
    
    printf("Inserisci un numero intero positivo: ");
    scanf("%d", &numero);
    
    if (numero <= 1) {
        printf("Il numero %d non è primo.\n", numero);
        return 0;
    }
    if (numero == 2) {
        printf("Il numero %d è primo.\n", numero);
        return 0;
    }
    if (numero % 2 == 0) {
        printf("Il numero %d non è primo.\n", numero);
        return 0;
    }

    int divisore = 3;
    int limite = sqrt(numero);
    while (divisore <= limite) {
        if (numero % divisore == 0) {
            printf("Il numero %d non è primo.\n", numero);
            return 0;
        }
        divisore += 2; // Controlliamo solo numeri dispari
    }

    printf("Il numero %d è primo.\n", numero);
    return 0;
}

Con queste ottimizzazioni, il programma diventa più efficiente, specialmente per numeri grandi. Abbiamo eliminato la necessità di contare i divisori fino alla fine e abbiamo ridotto il numero di operazioni di divisione. Inoltre, controlliamo solo i numeri dispari come divisori, riducendo ulteriormente il numero di operazioni.

Conclusioni

In conclusione, abbiamo sviluppato alcuno algoritmi per verificare se un numero è primo in C, implementando diverse strategie per migliorare l’efficienza dell’algoritmo. Queste ottimizzazioni includono:

Limitare la divisione alla radice quadrata del numero: Abbiamo ridotto il limite superiore della divisione al valore più vicino alla radice quadrata del numero da controllare, poiché se un numero ha un divisore maggiore di questo limite, deve necessariamente avere anche un divisore più piccolo.
Controllo della primalità solo per numeri dispari: Poiché tutti i numeri pari maggiori di 2 non sono primi, abbiamo controllato la primalità solo per numeri dispari, partendo da 3 e incrementando di 2 ad ogni iterazione.
Uscita anticipata dal ciclo: Abbiamo interrotto il ciclo non appena trovato un divisore, anziché contare tutti i divisori fino alla fine, per risparmiare tempo e operazioni.

Queste ottimizzazioni rendono il programma più efficiente, specialmente per numeri grandi, riducendo il numero di operazioni di divisione e controlli necessari. Con questo miglioramento, il programma è in grado di verificare se un numero è primo in modo più rapido ed efficiente.