Il problema di ProjectEuler n.216 richiede una forte ottimizzazione, efficienza del codice, oltre che logica matematica. ProjectEuler è molto interessante e oltre un certo livello dei problemi (dal 100-200 in su) richiede davvero un'attenta riflessione prima di trovare la strada migliore.
Qui possiamo avere un'implementazione del già citato calcolo parallelo, oltre a tutte le possibili ottimizzazioni di base dell'algoritmo.
Simile al caso già visto Calcolo lista numeri primi fino ad N: algoritmo più efficiente in C, qui si richiede di calcolare il totale di numeri primi minori di una funzione t(N)=2N2-1, con N=50milioni. Riportiamo il resto integrale:
Consider numbers t(n) of the form t(n) = 2n2-1 with n > 1.
The first such numbers are 7, 17, 31, 49, 71, 97, 127 and 161.
It turns out that only 49 = 77 and 161 = 723 are not prime.
For n ≤ 10000 there are 2202 numbers t(n) that are prime.
How many numbers t(n) are prime for n ≤ 50,000,000 ?
In linea generale, questi sono gli aspetti importanti considerati:
- ovviamente linguaggio C, l'efficienza è già critica (tempo di esecuzione totale del codice) quindi occorre scegliere a priori la soluzione migliore, non possiamo certo applicare Python o COBOL, per dirne uno 😄
- funzione che calcola i numeri primi, nel modo più efficiente possibile, come fatto qui (con eccezione di metodi basati sui crivelli, che però con numeri estremamente grandi ovvero 2N2-1 = 5*1015, non sarebbero più gestibili in termini di memoria)
- variabili allocate nel registro della CPU anziché nella RAM
- dimensione corretta delle variabili e non oltre (long int oppure solamente int o anche bool, a seconda della necessità)
- calcolo parallelo: sfruttiamo tutti i thread della CPU (in questo caso Dual Core 4 thread): quindi nel codice che segue, vediamo la sintassi
#pragma omp parallel { /* ciclo */ } dove il blocco, che nel codice va sulla riga sotto, contiene tutto il codice, iterazioni da far girare in parallelo; la compilazione in questo caso è gcc file.c -o file -lm -fopenmp, dove -lm indica la libreria di math.h e -fopenmp invece per il calcolo parallelo, per riconoscere la direttiva #pragma omp parallel
Si riporta tutto il codice in C:
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
bool is_prime(unsigned int numero) {
double radice = sqrt(numero);
if(numero%2==0){return false;}
for (register unsigned int i = 3; i <=radice; i+=2){
if (numero % i == 0) {
return false;
}
}
return true;
}
int main() {
register unsigned long int i=2;
register unsigned long int N=50000000;//Nmax
register unsigned int cont=0;
clock_t start = clock();
#pragma omp parallel //gcc -file.c -o file -lm -fopenmp
{
while(1){
if(2*i*i-1>=2*N*N-1){break;}else{
if (is_prime(2*i*i-1)){
cont++;
}
i++;
}
}
}
clock_t end = clock();
printf("%f s\n", (float)0.25*(end - start) / CLOCKS_PER_SEC); //4 threads
printf("%d\n", cont);
return 0;
}
Risultati:
- tempo di esecuzione del codice: 226 secondi
- risposta al problema ovvero totale numeri che rispettano la condizione cercata: 4751510
