programma c++

[lucianorossi]

devo fare un proggy per calcolare i numeri primi per la scuola
Ho fatto una prima bozza in turbopascal
processo i primi 10000 numeri in 12 secondi [p4 1560mhz]
l'ho ribattuto in C++
l'ho migliorato più che ho potuto
250000 numeri processati in 12 secondi [solito proc]
ora però ho un problema: come andare oltre 250000 numeri?
perchè li devo memorizzare in un'array, ma non posso mandarlo oltre 250000 perchè se no il programma non parte, e non posso nemmeno fare una array doppio indice, perchè non parte lo stesso.
C'è un limite alla memoria utilizzaa? si può aumentare?
Uso Visual C++

Allego il programma

[lucianorossi]

eccolo

[a2000]

(un milione) di numeri processat
PII 350 MHz[/siz]
interpretato n VBA

tempo di calcolo 0.88 secondi[/siz]

Interessa ?

[misterx]

Originally posted by "a2000"

(un milione) di numeri processat
PII 350 MHz[/siz]
interpretato n VBA

tempo di calcolo 0.88 secondi[/siz]

Interessa ?

impossibile; tempo troppo basso

[lucianorossi]

un milione in 1minuto e 7 secondi, per ora...

[lucianorossi]

è meglio fare un programma lungo che però faccia meno operazioni aritmetiche possibile o meglio farlo più corto e fargli fare un po' più di operazioni aritmetiche?

[misterx]

magari vedendo il sorgente in C++ si potrebbe capire qualcosa in più

[/\/\@®¢Ø]

Originally posted by "lucianorossi"

è meglio fare un programma lungo che però faccia meno operazioni aritmetiche possibile o meglio farlo più corto e fargli fare un po' più di operazioni aritmetiche?

Non e' possibile dire se sia meglio l'una o l'altra, dipende anche da quante volte ripeti le stesse operazioni. Piu' che contare le operazioni in questi casi e' meglio cercare l'algoritmo piu' adatto. Probabilmente il migliore e' la trivella di Eratostene (si chiama cosi' ? ), che suppongo sia la stessa tecnica che ha utilizzato a2000 (anzi, a onor del vero di questo argomento si era gia' parlato tempo fa, e mi sembra ne avesse accennato per primo lui)
L'idea e' abbastanza semplice: tieni una tabella di valori booleani che indichi se un numero e' primo o no. All'inizio tutti i valori della tabella sono veri, e man mano 'togli' tutti i multipli (per prima cosa togli i multipli di 2 poi quelli di 3 ... ).
Non dovrebbe risultare molto codice, 20 linee di codice basteranno.

[/\/\@®¢Ø]

Originally posted by "misterx"




impossibile; tempo troppo basso

No, mi sembra piu' che ragionevole

[a2000]

Originally posted by "/\/\@®¢Ø"


No, mi sembra piu' che ragionevole

ohhh /\/\@®¢Ø !

"almeno tu nell'universooooo ...." :o :o :o

[lucianorossi]

grazie tante, questo è il primo programma che ho ideato, e girava benissimo, solo che non potevo fare un array di + di 250000 valori, e a me serve per trovare valori fra 2^128 e 2^129
C'è un metodo per fare un array di 2^129 valori?

Attualmente il codice è molto ingarbugliato, ora lo posto ma non so se ci capirete qualcosa

[lucianorossi]

#include <stdio.h>

void main()

{
unsigned long int a, b, c, d, e, f, h;
unsigned long int numerip[250000];
bool primo;
FILE *fw;
printf("Prime_Numbers v0.7.0.3 build 35 \n");
printf("Totalmente programmato da Giorgio Busoni \n");
printf("L''intevallo di numeri nel quale vuoi cercare i numeri primi \n");
printf("Digita la cifra di fine intervallo (massima) \n");
scanf("%d", &b);
printf(&"Please wait \n");
a=1;
fw = fopen("Primenumbers.txt","w");
c=a; /*copia a in un'altra variabile per non sovrascrivere il valore originario di a*/
if (b<=2)
{
printf("Il numero deve essere maggiore di 2 \n");
}
else
{
h=1;
numerip[2]=2;
while(c<b){
if(c>=250000)
{
break;
}
d=3;
e=c/2;
primo=true; /*il numero viene classificato come primo*/
while(numerip[d]<=e){
f= c % numerip[d]; /*resto delle divisione del numero per d (variabile che va da 2 a c-1)*/
numerip[h]=0;
if (f==0) /*se il resto=0...*/
{
primo=false; /*e viene anche memorizzato nella variabile temporanea*/
break;
}
d=d+1; /*si aumenta i divisore di 1 prima di ripetere l'operazione*/
}
if (primo==true) /*se alla fine del clico il numero non ha mai dato resto 0 in una divisione*/
{
numerip[h]=c; /*e il numero viene elencato nell'array come primo*/
if (numerip[h]==1)
{
numerip[h]=2;
}
fprintf(fw,"%d, " , numerip[h]);
h=h+1;
}
c=c+2; /*si passa al numero successivo prima di ripetere il ciclo*/
printf("Ready %d % \r", ((c*100)/(a*b)));
}
while(c<b){
if(c>5000000000)
{
break;
}
d=3;
e=c/2;
primo=true; /*il numero viene classificato come primo*/
while(numerip[d]<=e){
if (numerip[d]==0)
{
break;
}
f= c % numerip[d]; /*resto delle divisione del numero per d (variabile che va da 2 a c-1)*/
if (f==0) /*se il resto=0...*/
{
primo=false; /*e viene anche memorizzato nella variabile temporanea*/
break;
}
d=d+1; /*si aumenta i divisore di 1 prima di ripetere l'operazione*/
}
if (primo==true) /*se alla fine del clico il numero non ha mai dato resto 0 in una divisione*/
{
fprintf(fw,"%d, " , c);
}
c=c+2; /*si passa al numero successivo prima di ripetere il ciclo*/
if(c<b)
{
printf("Ready %d % \r", ((c*100)/(b)));
}
}
numerip[1]=2;
printf("Ricerca numeri primi completata");
}
}

[a2000]

Originally posted by "misterx"




impossibile; tempo troppo basso

provare per credere.

interessa ?

[lucianorossi]

versione compilata e zippata aggiornata

[lucianorossi]

Originally posted by "a2000"



provare per credere.

interessa ?

si, se completo di codice

[a2000]

per ora il codice (12 righe).

Sub Primi()
 
  Const iMax& = 250000000
  Dim i As Long, j As Long
  Dim aaa(1 To iMax) As Byte
 
  For i = 2 To Sqr(iMax)
   If aaa(i) = 0 Then
    For j = 2 * i To iMax Step i
     aaa(j) = 1
    Next j
   End If
  Next i

End Sub

[a2000]

... adesso non ho tempo.

comunque, come sempre, l'algoritmo è TUTTO e ce ne sono tanti anche per intervalli numerici molto grandi.

ma la cosa divertente è comunque cimentarsi per trovare qualche soluzione personale e originale (ma semplice ed elegante).
con l'algoritmo del crivello di Eratostene naive il limite è la memoria di massa disponibile sulla macchina.
con qualche pensata sulla virtualizzazione del vettore aaa() e considerando che per valori di n molto grandi "quasi" tutti i numeri sono primi .... 2^129 non è poi così grande.

[a2000]

comunque qualcosa bisogna saperla:

http://matematica.uni-bocconi.it/betti/AKS.htm

[lucianorossi]

cosa vuol dire dim?
che linguaggio è?
sul visual c++ non parte correttamente

[/\/\@®¢Ø]

In C++ puoi usare qualcosa del genere, per il calcolo e la stampa.

#include <iostream>
#include <cmath>
#include <vector>
int main()
{
    unsigned long n = 1000000;
    bool data[n];
    fill( data , data + n , true );
    data[0] = data[1] = false;
    for ( unsigned long i=2 ; i < sqrt(n) ; ++i )
        if ( data[i] )
        {
            unsigned long m = i*2;
            do
            {
                data[m]=false;
                m+=i;
            }while( m < n );
        }
    for ( unsigned long i=0 ; i<n ; ++i )
        if (data[i] )
            cout << i << endl;
}

anche se cosi' come e' fatto non puoi arrivare a cifre dell'ordine del 2^128