Calcola Numero Primo In C

Verifica se un numero è primo e visualizza i risultati con analisi dettagliata

Guida Completa: Come Calcolare i Numeri Primi in C

I numeri primi sono fondamentali in matematica e informatica, specialmente in crittografia e algoritmi. Questa guida ti insegnerà come implementare diversi metodi per verificare i numeri primi in linguaggio C, con analisi delle prestazioni e ottimizzazioni.

Cos’è un Numero Primo?

Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori distinti: 1 e sé stesso. I numeri primi sono infiniti e giocano un ruolo chiave in:

• Crittografia (es. algoritmo RSA)
• Teoria dei numeri
• Generazione di numeri pseudo-casuali
• Ottimizzazione degli algoritmi

Metodi per Verificare i Numeri Primi in C

1. Metodo Base (O(n))

Il metodo più semplice ma meno efficiente:

#include <stdio.h> #include <stdbool.h> bool is_prime_basic(int n) { if (n <= 1) return false; for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } int main() { int num = 17; if (is_prime_basic(num)) { printf(“%d è un numero primo\n”, num); } else { printf(“%d non è un numero primo\n”, num); } return 0; }

2. Metodo Ottimizzato (O(√n))

Una versione migliorata che riduce il numero di iterazioni:

bool is_prime_optimized(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) { return false; } } return true; }

3. Crivello di Eratostene

Algoritmo efficiente per trovare tutti i numeri primi fino a un limite N:

void sieve_of_eratosthenes(int n) { bool prime[n+1]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) { prime[i] = false; } } } for (int p = 2; p <= n; p++) { if (prime[p]) { printf(“%d “, p); } } }

Confronto delle Prestazioni

Metodo	Complessità	Tempo per n=1,000,000 (ms)	Memoria	Migliore per
Metodo Base	O(n)	~4500	O(1)	Numeri molto piccoli
Metodo Ottimizzato	O(√n)	~12	O(1)	Verifica singoli numeri
Crivello di Eratostene	O(n log log n)	~80	O(n)	Generare primi in intervalli

Ottimizzazioni Avanzate

Per applicazioni critiche, considera queste tecniche:

1. Precalcolo: Memorizza i primi in una lookup table
2. Probabilistico: Usa test come Miller-Rabin per numeri molto grandi
3. Parallelizzazione: Dividi il range tra più thread
4. Bitwise Sieve: Usa array di bit per risparmiare memoria

Applicazioni Pratiche in C

Ecco un esempio completo che combina input utente e visualizzazione:

#include <stdio.h> #include <stdbool.h> #include <math.h> bool is_prime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; } int main() { int num; printf(“Inserisci un numero: “); scanf(“%d”, &num); if (is_prime(num)) { printf(“%d è un numero primo\n”, num); // Trova i primi successivi printf(“I prossimi 5 numeri primi sono: “); int count = 0, current = num + 1; while (count < 5) { if (is_prime(current)) { printf(“%d “, current); count++; } current++; } } else { printf(“%d non è un numero primo\n”, num); printf(“I divisori sono: 1”); for (int i = 2; i <= num; i++) { if (num % i == 0) printf(“, %d”, i); } } return 0; }

Errori Comuni da Evitare

• Dimenticare i casi edge: 0, 1, 2 e numeri negativi
• Overflow degli interi: Usa long long per numeri grandi
• Ottimizzazioni premature: Il metodo base è sufficiente per n < 1000
• Ignorare la memoization: Cache i risultati per chiamate ripetute

Risorse Accademiche

Per approfondire la teoria dei numeri primi:

• Corso di Teoria dei Numeri – UC Berkeley
• Standard Crittografici – NIST (.gov)
• Duke Mathematical Journal – Ricerche sui primi

Domande Frequenti

Q: Qual è il numero primo più grande conosciuto?

A: Al 2023, è 2^82,589,933GIMPS).

Q: Perché il crivello è più veloce per intervalli?

A: Elimina multipli di primi già trovati, riducendo le operazioni da O(n√n) a O(n log log n).

Q: Come gestire numeri primi molto grandi in C?

A: Usa librerie come GMP (gmplib.org) per aritmetica a precisione arbitraria.

Q: Esistono formule per generare primi?

A: No, ma ci sono polinomi che generano molti primi (es. n² − n + 41 per n=0..40).