Ciao a tutti. Sono di nuovo alle prese con i numeri primi.
Ho creato un programma in C che, tramite il crivello di Eratostene trova il numero di numeri primi tra 3 e un numero.
Il sostanza, il programma immagazzina in un vettore tutti i numeri dispari tra 3 e N, poi trovo tutti i numeri primi compresi tra 3 e la radice quadrata di N e li metto in una lista.
A questo punto cancello dal vettore tutti i numeri multipli dei primi nella lista e i numeri rimanenti sono i primi.
A questo punto, però, mi si pone un problema: La consegna iniziale dell'esercizio, era di trovare il numero di numeri primi tra 3 e un numero N con N tra le 14 e le 19 cifre quindi un long int.
Se non sbaglio a fare i conti:
Mettendo come N il numero 12345678912345 (14 cifre), e immagazzinando nel vettore solo i dispari, dovrei fare:

(12345678912345 / 2) = 6,17283946 × 10^12
cosi trovo il numero dei dispari, e poi:
(6,17283946 × 10^12) * 8 = 4.93827156 × 10^13
Infatti ogni long int è 8 byte.
Se non sbaglio a contare gli "zeri" dovrebbe essere un numero vicino a 50'000'000'000'000 Byte --> 50 TeraByte.
  Qualcuno ha 50 Tera Byte di RAM da prestarmi? 

Il mio pensiero, a l'inizio, fu quello di dividere il vettore in blocchi da poche decine di migliaia di numeri e poi, per compensare un po sotto l'aspetto velocità, avrei messo dei thread che cancellavano i numeri (il thread1 cancella tutti i multipli di 3 e 5, il thread2 cancella tutti i multipli di 7 e 11 e così via).
Secondo voi è la soluzione ottimale o dovrei optare per un programma più CPU Bound?
Il fatto è che mi piaceva l'idea del crivello di Eratostene per prendere un po più di famigliarità con le liste e i puntatori.

Grazie a tutti e buone feste!

Ho provato questa via alternativa: Creo un vettore di N posizioni tutte inizializzate a true. Scorro l'indici del vettore da 2 a N e se l'indice non è primo metto a False la cella del vettore corrispondente. Alla fine del programma conto i TRUE rimasti e ho il numero di numeri primi. La cosa funziona alla perfezione con numeri piccoli, ma con numeri grandi (anche ad esempio 123456 che il precedente programma faceva), mi da un segmentation fault Ora provo a cercare "cache oblivious sieve of eratosthenes".
Intanto se hai soluzione per il segmentation fault fammi sapere
Grazie!!

Grazie della risposta.
Mi chiedevo se per compiti del genere (calcolo dei numeri primi tra 0 e un numero molto grande) fosse meglio creare programmi CPU bound oppure programmi che fanno largo uso delle memoria.
Ho notato che applicando il crivello di Eratostene (nel quale il processore fa ben poco ma si occupa molta RAM) per svolgere il compito da me prefissato, i tempi si riducono notevolmente se il numero è relativamente piccolo (non più di 300.000), mentre per numeri molto più grandi (oltre le 14 cifre), un programma che sfrutta molto la CPU (nel mio caso ho creato un programma che divide in blocchi la serie di numeri da analizzare e poi dei thread opportunamente sincronizzati analizzano) la fa da padrona.
Secondo te, quindi, dovrei concentrarmi, considerando che la consegna è "trovare i numeri primi da 0 a N con N sopra le 14 cifre" su una soluzione tipo il crivello di Eratostene (ottimizzando l'algoritmo come hai detto tu sopra) oppure su una soluzione che fa largo utilizzo di CPU (ottimizzare il mio algoritmo che divide in blocchi ecc..)?
Grazie ancora!

Ecco spiegato l'algoritmo che sfrutta la CPU:
L'utente inserisce il numeri a cui vuole arrivare nel calcolo.
il programma calcola i numeri primi tra 2 e la radice quadrata di N e li salva in una lista.
Ora il programma divide in blocchi il numero e ad ogni blocco assegna un thread. (es. se inserisco 100 000, il programma suddivide il numero 100 000 in 10 blocchi da 10 000. Il primo thread controlla quali primi ci sono tra 0 e 10 000, il secondo tra 10 001 e 20 000 ecc...).
Ovviamente per evitare corse critiche ho applicato delle MUTEX.
Il singolo thread prende in considerazione i numeri dispari di ogni blocco e prova a dividere ogni numero dispari per tutta la lista dei primi (e qui dovrei migliorare l'algoritmo): se una divisone da come resto 0, vuol dire che il numero non è primo.
Ora provo ad informarmi per bene sull'algoritmo che mi hai segnalato.
Grazie Ancora!

Ti faccio notare che l'algoritmo da te descritto è praticamente quello a cui facevo riferimento e che non richiede più calcoli del crivello di eratostene in quanto è semplicemente il crivello di eratostene con l'ordine delle operazioni cambiato. Rispetto al crivello di eratostene "standard" ha però il vantaggio di accedere alla memoria in modo più localizzato. Nota che non hai bisogno di alcun tipo di sincronizzazione se i thread accedono alla lista dei primi sotto la radice del numero in sola lettura e accedono in modo indipendente al bitvector finale. Questa versione è in generale preferibile rispetto alla versione standard quando il numero massimo è molto alto. Utilizzerei comunque un metodo diverso per escludere i primi rispetto alla tua idea di dividere ogni numero per ogni primo. Per ogni primo, cercherei il primo multiplo dispari all'interno dell'intervallo e sommerei quindi al numero due volte il numero primo (in modo da avere un'altro numero dispari) per eliminare tutti i multipli successivi in modo simile a come si fa nel crivello di eratostene standard.