C/C++ - Numeri primi Multithread?

Non è facile parallelizzare un crivello comunque. Penso che il massimo che puoi fare sia parallelizzare la parte di crossing out (quando escludi i multipli).
Se il limite superiore è grande, potrebbe convenire parallelizzare questa operazione stessa, ma vedo pochissimi vantaggi.
Si possono in alternativa parallelizzare questi processi sapendo che se ti trovi su n, tutti i numeri nella tabella fino a n^2 sono già definitivamente primi oppure non primi(e quindi puoi già fare il crossing out dei loro multipli).

Se non stai usando un crivello il discorso cambia però. In generale, è difficile perché non puoi suddividere la ricerca arbitrariamente.

Se è vero che quella prova funziona solo fino al 49 (che non è primo, 7*7=49) allora l'unica è provare tutti i naturali dispari e il 2 fino a radice quadrata di n, se una divisione con uno di quei numeri non ha resto il numero NON è primo.

Postato originariamente da TheDarkJuster:

Se è vero che quella prova funziona solo fino al 49 (che non è primo, 7*7=49) allora l'unica è provare tutti i naturali dispari e il 2 fino a radice quadrata di n, se una divisione con uno di quei numeri non ha resto il numero NON è primo.

si ma se salgo molto (tipo a sopra 1milione) il multithreading non varrà di certo quanto ottengo usando il mio algoritmo mi sa..

[quotePostato originariamente da lumo:
Non è facile parallelizzare un crivello comunque. Penso che il massimo che puoi fare sia parallelizzare la parte di crossing out (quando escludi i multipli).
Se il limite superiore è grande, potrebbe convenire parallelizzare questa operazione stessa, ma vedo pochissimi vantaggi.
Si possono in alternativa parallelizzare questi processi sapendo che se ti trovi su n, tutti i numeri nella tabella fino a n^2 sono già definitivamente primi oppure non primi(e quindi puoi già fare il crossing out dei loro multipli).

Se non stai usando un crivello il discorso cambia però. In generale, è difficile perché non puoi suddividere la ricerca arbitrariamente.

Mmmhh... dovrei cambiare la struttura dell'algoritmo come suggeriva prima TheDarkJuster, ma comunque sarebbe un cambio enorme.. probabilmente il mio algoritmo cesserebbe di essere e si trasformerebbe un tutt'altro algoritmo

Si, se un algoritmo non è fatto per essere parallelizzato o lo cambi o non parallelizzi il calcolo, semplice.

Calcolando i numeri primi fino ad un milione, trovo quasi 80.000 primi. Senza usare i primi, ma tutti i numeri dispari e 2 si dovrebbero analizzare invece 500.000 numeri.
Calcolando i numeri primi fino a 10 milioni, trovo quasi 665.000 primi. Senza usare i primi, ma tutti i numeri dispari e 2 si dovrebbero analizzare invece 5000.000 numeri.
Calcolando i numeri primi fino a 100 milioni, trovo quasi 5.750.000 primi. Senza usare i primi, ma tutti i numeri dispari e 2 si dovrebbero analizzare invece 50000.000 numeri.

Se lavorassi sfruttando circa 30 cores, allora avrebbe senso lavorare senza sfruttare i primi, altrimenti no.
Visto che come si nota, più si va vanti e più i numeri prima diminuiscono e quindi il carico di lavoro diventa proporzionalmente minore.

Ok, e direi che con questo abbiamo chiuso e io ho sprecato tanti giorni inutilmente xD

Grazie a tutti per il supporto comunque

Non hai sprecato giorni. La prossima volta che ti si presenta un problema simile sai se vale la pena di affrontarlo o è meglio non provarci nemmeno.

Hai dovuto rispolverare pthread e i mutex. Chiamalo tempo sprecato.....

Un'implementazione comoda multipiattaforma può essere OpenMP.

Invece di gestire i thread e la sincronizzazione a mano, bisogna solo specificare i kernel di esecuzione tramite direttive #pragma.
In questo modo ragioni più sull'algoritmo e meno sui dettagli tecnici, ottenendo comunque prestazioni elevate se l'algoritmo si presta.