Calcolatore Algoritmo Numeri Primi in C

Strumento professionale per analizzare l’efficienza degli algoritmi di calcolo dei numeri primi in linguaggio C. Ottimizza le prestazioni del tuo codice con dati precisi e visualizzazioni interattive.

Numero massimo da analizzare

Seleziona algoritmo

Livello di ottimizzazione

Numero di thread (per algoritmi paralleli)

Risultati del Calcolo

Algoritmo utilizzato: Crivello di Eratostene

Numero massimo analizzato: 1000

Numeri primi trovati: 168

Tempo di esecuzione stimato (C): 0.002 ms

Complessità algoritmica: O(n log log n)

Memoria utilizzata: 1.2 KB

Guida Completa agli Algoritmi per il Calcolo dei Numeri Primi in C

I numeri primi rappresentano uno dei concetti fondamentali della teoria dei numeri e della crittografia moderna. La loro identificazione efficienti è cruciale per applicazioni che vanno dalla sicurezza informatica alla teoria dei numeri computazionale. Questo articolo esplora in profondità gli algoritmi più efficaci per il calcolo dei numeri primi implementabili in linguaggio C, con particolare attenzione alle ottimizzazioni e alle prestazioni.

1. Fondamenti Teorici dei Numeri Primi

Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori distinti: 1 e sé stesso. Le proprietà dei numeri primi includono:

Infinitudine: Euclide dimostrò che esistono infiniti numeri primi (circa 300 a.C.)
Distribuzione: Il teorema dei numeri primi descrive la distribuzione asintotica
Fundamental Theorem of Arithmetic: Ogni numero intero >1 è un prodotto unico di numeri primi
Applicazioni crittografiche: RSA, Diffie-Hellman, ECC si basano sulla difficoltà di fattorizzare grandi numeri

Risorsa Accademica:

Il Dipartimento di Matematica dell’Università di Berkeley offre risorse approfondite sulla teoria dei numeri primi, inclusi materiali didattici sul Crivello di Eratostene e algoritmi moderni.

2. Algoritmi Classici per il Calcolo dei Numeri Primi

2.1 Divisione per Tentativi (Trial Division)

L’algoritmo più semplice ma meno efficiente. Per determinare se un numero n è primo, si dividono tutti i numeri da 2 a √n:

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

Complessità: O(√n) per numero
Vantaggi: Semplice da implementare
Svantaggi: Estremamente lento per numeri grandi

2.2 Crivello di Eratostene (Sieve of Eratosthenes)

Algoritmo efficiente per trovare tutti i numeri primi fino a un limite n. Funziona marcando iterativamente i multipli di ogni primo trovato:

void sieve_of_eratosthenes(int n, bool* primes) {
    memset(primes, true, (n+1) * sizeof(bool));
    primes[0] = primes[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (primes[p]) {
            for (int i = p * p; i <= n; i += p)
                primes[i] = false;
        }
    }
}

Complessità: O(n log log n)
Ottimizzazioni:

Segmented Sieve per grandi intervalli
Bit-level compression per ridurre la memoria
Parallelizzazione con OpenMP

Algoritmo	Complessità	Memoria	Pratico per n <
Trial Division	O(√n)	O(1)	10⁶
Crivello di Eratostene	O(n log log n)	O(n)	10⁸
Miller-Rabin	O(k log³n)	O(1)	10²⁰
AKS Primality Test	O(log^7.5n)	O(log n)	Teorico

3. Algoritmi Probabilistici e Deterministici Avanzati

3.1 Test di Primalità di Miller-Rabin

Algoritmo probabilistico che determina se un numero è probabilmente primo. Per k iterazioni, l'errore è ≤ 4^-k:

bool miller_rabin(uint64_t n, int k) {
    if (n < 2) return false;
    if (n != 2 && n % 2 == 0) return false;

    uint64_t d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    for (int i = 0; i < k; i++) {
        uint64_t a = 2 + rand() % (n - 4);
        uint64_t x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (int j = 0; j < s - 1; j++) {
            x = mod_pow(x, 2, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

Vantaggi:

Molto più veloce di Trial Division per numeri grandi
Accuratezza configurabile
Implementazione relativamente semplice

3.2 Test di Primalità AKS

Primo algoritmo deterministico con complessità polinomiale (2002). Nonostante la complessità teorica favorevole (O(log^7.5n)), in pratica è più lento di Miller-Rabin per numeri < 10²⁰:

// Implementazione semplificata (non ottimizzata)
bool aks_primality(uint64_t n) {
    if (is_perfect_power(n)) return false;

    uint64_t r = find_smallest_r(n);
    uint64_t max_k = floor(sqrt(phi(r)) * log2(n));

    for (uint64_t a = 2; a <= max_k; a++) {
        if (gcd(a, n) > 1) return false;
        if (mod_pow(a, n, r) != mod_pow(a, 1, r)) return false;
    }
    return true;
}

Documentazione Ufficiale:

Il National Institute of Standards and Technology (NIST) pubblica linee guida sulla crittografia basata su numeri primi, inclusi standard per la generazione di chiavi sicure.

4. Ottimizzazioni per Implementazioni in C

Le prestazioni degli algoritmi in C possono essere significativamente migliorate con queste tecniche:

Ottimizzazioni del compilatore:
- Utilizzare -O3 -march=native con GCC/Clang
- Abilitare le estensioni SIMD (-msse4.2 -mavx2)
Gestione della memoria:
- Allocazione statica per array di dimensioni note
- Utilizzare calloc invece di malloc + memset
Parallelizzazione:
- OpenMP per il Crivello di Eratostene
- Thread pool per test di primalità indipendenti
Ottimizzazioni algoritmiche:
- Precalcolo di piccoli primi per Trial Division
- Wheel factorization (es. saltare multipli di 2, 3, 5)

// Esempio di wheel factorization (2,3,5)
const int wheel[] = {4, 2, 4, 2, 4, 6, 2, 6};
for (int i = 7; i <= limit; i += wheel[(i-7)%8]) {
    // Test di primalità solo per i non divisibili per 2,3,5
}

5. Benchmark e Confronto delle Prestazioni

I seguenti dati rappresentano tempi medi di esecuzione su un processore Intel i9-12900K (single-threaded):

Algoritmo	n = 10⁶	n = 10⁸	n = 10¹²	Memoria (n=10⁸)
Trial Division (naive)	12.45 s	1245 s	N/A	1 MB
Trial Division (ottimizzato)	1.87 s	187 s	N/A	1 MB
Crivello di Eratostene	0.002 s	0.24 s	24 s	120 MB
Segmented Sieve	0.003 s	0.04 s	4.1 s	15 MB
Miller-Rabin (k=20)	N/A	N/A	0.0001 s	1 KB

Osservazioni:

Il Crivello domina per intervalli fino a 10⁹
Miller-Rabin è imbattibile per numeri > 10¹⁵
Le ottimizzazioni riducono i tempi di Trial Division del 85%
La memoria diventa il colli di bottiglia per il Crivello con n > 10⁹

6. Implementazione Pratica in C: Esempio Completo

Il seguente codice implementa un Crivello di Eratostene segmentato con ottimizzazioni:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#include <time.h>

#define SEGMENT_SIZE (1 << 20) // 1MB segment

void segmented_sieve(uint64_t n) {
    uint64_t limit = sqrt(n) + 1;
    bool *base_primes = calloc(limit + 1, sizeof(bool));

    // Crivello base per radice(n)
    for (uint64_t p = 2; p <= limit; p++) {
        if (!base_primes[p]) {
            for (uint64_t i = p * p; i <= limit; i += p)
                base_primes[i] = true;
        }
    }

    // Crivello segmentato
    uint64_t count = (n >= 2) ? 1 : 0; // 2 è primo
    for (uint64_t low = 3; low <= n; low += 2 * SEGMENT_SIZE) {
        uint64_t high = (low + 2 * SEGMENT_SIZE - 1) & ~(2 * SEGMENT_SIZE - 1);
        if (high > n) high = n;

        bool *segment = calloc(SEGMENT_SIZE, sizeof(bool));

        for (uint64_t p = 3; p <= limit; p += 2) {
            if (!base_primes[p]) {
                uint64_t first_multiple = (low % p) ? low + (p - low % p) : low;
                if (first_multiple == p) first_multiple += p;
                for (uint64_t j = first_multiple; j <= high; j += 2 * p) {
                    if (j != p) segment[j - low] = true;
                }
            }
        }

        for (uint64_t i = low; i <= high; i += 2) {
            if (!segment[i - low]) count++;
        }

        free(segment);
    }

    printf("Numeri primi fino a %lu: %lu\n", n, count);
    free(base_primes);
}

int main() {
    clock_t start = clock();
    segmented_sieve(1000000000);
    clock_t end = clock();
    printf("Tempo impiegato: %.3f secondi\n", (double)(end - start) / CLOCKS_PER_SEC);
    return 0;
}

Compilazione ottimizzata:
gcc -O3 -march=native -mtune=native sieve.c -o sieve -lm

7. Applicazioni Pratiche e Caso d'Uso Reale

Gli algoritmi per numeri primi trovano applicazione in:

Crittografia:
- Generazione di chiavi RSA (prodotto di due primi grandi)
- Curve ellittiche (ECC) per Bitcoin e blockchain
- Protocollo Diffie-Hellman per scambio chiavi
Teoria dei Numeri Computazionale:
- Fattorizzazione di grandi numeri
- Test di primalità per numeri di Mersenne
- Ricerca di primi gemelli e altre congetture
Applicazioni Ingegneristiche:
- Generazione di numeri pseudo-casuali
- Hash table con dimensioni prime per ridurre collisioni
- Algoritmi di compressione dati

Risorsa Governativa:

Il Computer Security Resource Center del NIST pubblica standard crittografici basati su numeri primi, inclusi FIPS 186-5 per la generazione di chiavi DSA.

8. Errori Comuni e Best Practice

Errori frequenti nell'implementazione:

Overflow degli interi: Usare sempre uint64_t per numeri > 2³²
Condizioni di terminazione errate: Il loop dovrebbe andare fino a √n, non n/2
Gestione della memoria: Dimenticare di deallocare array grandi nel Crivello
Parallelizzazione naif: Condivisione non sicura di variabili tra thread
Precisione nei test probabilistici: Usare troppo poche iterazioni in Miller-Rabin

Best practice:

Validare sempre gli input (n ≥ 2)
Usare funzioni inline per operazioni critiche
Preferire bit array a boolean array per risparmiare memoria
Implementare cache-friendly algorithms (località spaziale)
Testare con numeri edge case (2, 3, numeri di Carmichael)

9. Futuro degli Algoritmi per Numeri Primi

Le aree di ricerca attive includono:

Algoritmi quantistici:
- Algoritmo di Shor per fattorizzazione in tempo polinomiale
- Implicazioni per la crittografia post-quantistica
Ottimizzazioni hardware:
- Accelerazione GPU per crivelli
- FPGA per test di primalità
Nuovi test deterministici:
- Miglioramenti dell'AKS con complessità inferiore
- Algoritmi basati su curve ellittiche
Applicazioni in IA:
- Generazione di numeri primi per reti neurali
- Crittografia omomorfica

10. Conclusioni e Raccomandazioni Finali

Scegliere l'algoritmo giusto:

n < 10⁷: Crivello di Eratostene (anche naive)
10⁷ < n < 10¹²: Crivello segmentato
n > 10¹²: Miller-Rabin con k=20-40
Applicazioni crittografiche: Sempre Miller-Rabin o test deterministici per numeri < 2⁶⁴

Ottimizzazioni consigliate:

Per Crivello: segmented + wheel factorization + bit packing
Per Miller-Rabin: precalcolo di moduli e uso di montgomery reduction
Generale: profiling con perf/gprof per identificare colli di bottiglia

La scelta dell'algoritmo dipende sempre dal contesto specifico: le dimensioni dei numeri in gioco, i requisiti di accuratezza, le risorse hardware disponibili e se si tratta di un'applicazione single-shot o ripetuta. Per la maggior parte delle applicazioni pratiche in C, una combinazione di Crivello segmentato per la precomputazione e Miller-Rabin per i test individuali offre il miglior compromesso tra velocità e accuratezza.

Algoritmo Calcolo Numeri Primi C