Congettura di Goldbach in C

[Mrhaha]

Ragazzi fra pochi avrei un esame di informatica che riguarda la programmazione in C,così per allenarmi ho pensato di scrivere un programma che mi trovasse un controesempio. E se non esistesse povero computer.
Arrivo ad un certo punto,il pc rallenta la ricerca di moltissimo,come potrei migliorarlo?

# include <stdio.h>
# include <stdlib.h>

int main (void){
     int i,x,k,prop,j,*primi,counter,z,propprime,p,propgold;
     printf ("Ha inizio l'operazione!\n");
     prop=1;
     i=4;
     while (prop==1){
           counter=0;
           printf ("Lavoriamo su %d\n",i);
           for (j=2; j<i-1; j++){
               p=2;
               propprime=0;
               while ((propprime==0)&&(p<=j/2)){
                     propprime=(p%j==0);
                     p++;
                     }
                     if (propprime)
                     counter++;
           }
           primi =(int*) malloc (sizeof(int)* counter);
           j=0;
           while((j<counter)&&(propgold==0)){
               z=j;
               propgold=0;
               while ((propgold==0)&&(z<counter)){
                     propgold=(primi[z]+primi[j]==i?1:0);
                     z++;
                     }
                     j++;
                     }
                     if (propgold){
                     printf ("per ora è vera!!! Dato che è somma di %d + %d\n",primi[z],primi[j]);
                     }else{
                     prop=propgold;
                     }
                     free(primi);
                     i=i+2;;
                     }
                     if (!prop)
                     printf ("%d,non vale la congettura di Goldbach!");
                     system ("PAUSE");
                     return 0;
                     }

Grazie!

[menale1]

Il programma va e per questo te ne faccio i complimenti . Prova a verificare cambiano piattaforma IDE !

[Mrhaha]

Emmm..sarebbe?

[apatriarca]

Oltre alla richiesta di usare i tag code, ti faccio notare che la congettura è stata "provata" fino a numeri dell'ordine di \(10^{18}\) e sono stati usati computer e algoritmi ben più potenti del tuo per fare il test e programmi probabilmente più efficienti. Da un occhiata veloce immagino che i rallentamenti potrebbero essere dovuti ad un uso massiccio della memoria. La seguente riga spaventa abbastanza:

primi =(int*) malloc (sizeof(int)* counter);

Ti consiglio di puntare a problemi di tipo diverso. Quali sono i tuoi interessi (matematici e non)? Non è difficile inventarsi nuovi problemi informatici da affrontare.

[menale1]

Credo che il problema sia proprio di memoria !!!

[Mrhaha]

apatriarca il mio intento sicuramente non era trovare il controesempio alla congettura di Goldbach (ammettendo che esista!).
E' un modo per unire l'algebra e l'informatica,che per ora mi sembravano due mondi un pò lontani.
Non capisco perchè quella riga ti spaventi! C'è qualcosa che ho sbagliato? A me piace tanto l'algebra,ma piace molto anche l'informatica! Se hai qualche idea per qualche programma dici pure,mi piace mettermi alla prova,e magari se ti va ne discutiamo insieme,magari anche insieme al menale!

[apatriarca]

Mi “spaventa” nel senso che mi fa subito pensare ad un uso incontrollato della memoria. Ad una prima occhiata non avevo visto che l'avevi poi deallocato e pensavo stessi usando una quantità esponenziale di memoria.. Ma per fortuna mi sbagliavo. Ci sono però altre parti del codice che non mi convincono. Accedi per esempio a primi senza averlo mai inizializzato da nessuna parte! Per quanto riguarda l'applicazione dell'informatica all'algebra mi terrei lontano dalla teoria dei numeri che tende a richiedere il supporto a interi di dimensione qualsiasi. Si può forse fare qualcosa sui polinomi, o su qualche gruppo. Magari qualcosa di crittografia (ad esempio quella sulle curve ellittiche).

[Mrhaha]

Capisco! Un esempio?

[apatriarca]

Un esempio su cosa esattamente? L'algebra è abbastanza vasta.. e non ho idea di quale siano le tue conoscenze.

[menale1]

Io proporrei sulla congettura di Cataldi ! Che ne dite ?

[apatriarca]

Non credo di averla mai sentita, di che cosa si tratta?

[Mrhaha]

Mmmm...cioè?

[apatriarca]

Mi sono appena ricordato di un sito che potreste trovare interessante: Project Euler. Contiene parecchi problemi matematici pensati per essere risolti facendo uso di un programma. Ne avevo risolti circa 150 (non in ordine) qualche tempo fa prima di stancarmi per imparare un po' haskell. I primi se non ricordo male sono abbastanza semplici ma diventano in fretta più difficili (non sono però ordinati per difficoltà.. gli ultimi non sono necessariamente più difficili di quelli di mezzo per esempio.. sono solo gli ultimi usciti).

[Mrhaha]

Grazie di cuore apatriarca! Solo un'ultima cosa..cos'è "haskell"?

[apatriarca]

Questo linguaggio

[Mrhaha]