prime numbers

Un forum per discutere di tutto quello che non riguarda la matematica!

Moderatore: tutor

Bloccato
lucianorossi
Messaggi: 195
Iscritto il: 01 gen 1970, 01:00
Località: Livorno
Contatta:

Messaggio da lucianorossi »

Sapete come fare un programma per calcolare i numeri primi compresi fra a e b usando Visual C++?
<BR>Il codice attualmente è questo:
<BR>
#include <stdio.h>
<BR>
<BR>void main()
<BR>
<BR>{
<BR>unsigned long int a, b, c, d, e, f, i, h;
<BR>unsigned long int range[2], numerip[250000] ;
<BR>bool primo;
<BR>FILE *fw;
<BR>printf(\"Prime_Numbers v0.5.1 build 3 \\n\");
<BR>printf(\"Totalmente programmato da Giorgio Busoni \\n\");
<BR>printf(\"L\'\'intevallo di numeri nel quale vuoi cercare i numeri primi \\n\");
<BR>printf(\"Digita la cifra di partenza (minima) \\n\");
<BR>scanf(\"%d\", &range[0]);
<BR>printf(\"Digita la cifra di arrivo (massima) \\n\");
<BR>scanf(\"%d\", &range[1]);
<BR>printf(&\"Please wait \\n\");
<BR>a=range[0];
<BR>b=range[1];
<BR>fw = fopen(\"Primenumbers.txt\",\"w\");
<BR>c=a; /*copia a in un\'altra variabile per non sovrascrivere il valore originario di a*/
<BR>/*if (c<=2) /*caso speciale a=2 poichè se no non verrebbe riconosciuo come primo*/
<BR>//{
<BR> //printf(\"Il numero \");
<BR> //printf(\"%d \" ,c);
<BR> //printf(\" è primo\");
<BR> //numerip[2]=true;
<BR>//}
<BR>h=1;
<BR>while(c<b)
<BR>{
<BR> d=2;
<BR> e=c/2;
<BR> primo=true; /*il numero viene classificato come primo*/
<BR> while(numerip[d]<=e){
<BR> f= c % numerip[d]; /*resto delle divisione del numero per d (variabile che va da 2 a c-1)*/
<BR> numerip[h]=0;
<BR> if (f==0) /*se il resto=0...*/
<BR> {
<BR> //printf(\"il numero \");
<BR> //printf(\"%d \" , c);
<BR> //printf(\" non Š primo, perchŠ divisibile per \");
<BR> //printf(\"%d \" , d); /*...allora viene scritto che il numero non è primo*/
<BR> //printf(\"\\n\");
<BR> primo=false; /*e viene anche memorizzato nella variabile temporanea*/
<BR> }
<BR> /*il numero viene inserito nell\'elenco come non-primo*/
<BR> d=d+1; /*si aumenta i divisore di 1 prima di ripetere l\'operazione*/
<BR> }
<BR> if (primo==true) /*se alla fine del clico il numero non ha mai dato resto 0 in una divisione*/
<BR> {
<BR> //printf(\"Il numero \"); /*il programma scrive che il numero è primo*/
<BR> //printf(\"%d \" , c);
<BR> //printf(\" Š primo \\n\");
<BR> numerip[h]=c; /*e il numero viene elencato nell\'array come primo*/
<BR> h=h+1;
<BR> }
<BR> c=c+1; /*si passa al numero successivo prima di ripetere il ciclo*/
<BR> printf(\"Ready : %d % \\r\", ((c*100)/(a*b)));
<BR>}
<BR>printf(\"I numeri primi compresi fra \");
<BR>printf(\"%d \" ,a);
<BR>printf(\" e \");
<BR>printf(\"%d \" ,b);
<BR>printf(\" sono: \\n\");
<BR>i=1;
<BR>while (i<=b)
<BR>{
<BR> if (numerip==1)
<BR> {
<BR> i=i+1;
<BR> }
<BR> if (numerip>0)
<BR> {
<BR> if (numerip<b) /*se nell\'elenco dell\'\'array alla voce il numeo è elencato come primo*/
<BR> {
<BR> printf(\"%d, \" ,numerip); /*il programma scrive che è primo (segue uno spazio)*/
<BR> fprintf(fw,\"%d, \" , numerip);
<BR> }
<BR> }
<BR> i=i+1; /*si aumenta i prima di ripetere il ciclo*/
<BR>}
<BR>}
<BR>

<BR>ma non posso andare oltre 250000 in questo modo
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Un programma l\'ho fatto io simile ( ma che arriva fino a 2*10^12) con il Turbo Pascal.
<BR>
<BR>Se ti interessasse...scrvilo sul forum <IMG SRC="images/forum/icons/icon_razz.gif">
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Un programma l\'ho fatto io simile ( ma che arriva fino a 2*10^12) con il Turbo Pascal.
<BR>
<BR>Se ti interessasse...scrvilo sul forum <IMG SRC="images/forum/icons/icon_razz.gif">
lucianorossi
Messaggi: 195
Iscritto il: 01 gen 1970, 01:00
Località: Livorno
Contatta:

Messaggio da lucianorossi »

tempo di ricerca? il mio ora esamina i numeri da 1 a 1000000 in 16 secondi
<BR>
<BR>se il tempo è genuino, posta!
Biagio
Messaggi: 535
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Biagio »

a proposito di programmi... in turbo pascal ho fatto un progaramma che scompone numeri in fattori primi in un max di circa 6/7 secondi e un altro che scompone ogni pari in tutte le somme possibili di due primi(congettura di Goldbach), se a qualcuno interessano....
<BR>ps: il max numero inseribile è quello consentito dalla variabile più capiente per num. interi:il max credo sia un po\' più di due miliardi<BR><BR>[ Questo Messaggio è stato Modificato da: Biagio il 16-05-2003 14:53 ]
Biagio
Messaggi: 535
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Biagio »

x simo: ma che cavolo di variabile usi per arrivare fino a 2*10^12???
Alex85
Messaggi: 197
Iscritto il: 01 gen 1970, 01:00
Località: Roma eur
Contatta:

Messaggio da Alex85 »

mah, in c++ puoi facilmente combinare tutte le variabili che vuoi o creare variabili enormi (e quindi ridefinire le operazioni principali), di solito io uso numeri a 8 byte. in teoria è fattibile anche fare un programma che macina numeri di qualsiasi grandezza (ovviamente intendo sempre con tutte le cifre significative).
<BR>in pascal, è tutto un poco più difficile, ma si dovrebbe poter fare.
<BR>
<BR>alex
J4Ck202
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da J4Ck202 »

In TP puoi ridefinire le operazioni aritmetiche elementari (somma differenza prodotto modulo) come funzioni che operano su stringhe, e utilizzando magari la base esadecimale arrivare a smanettare su numeri nell\'ordine di 2^1000.. ma servono tante conversioni e tantissima pazienza..
acarus
Messaggi: 106
Iscritto il: 01 gen 1970, 01:00
Località: Molto lontano ...

Messaggio da acarus »

In C++, si può pensare di attuare l\'overloading di un\'operazione ricorsiva di calcolo dei numeri primi: non è una cosa semplicissima ne tanto meno veloce <IMG SRC="images/forum/icons/icon_eek.gif">
<BR>In ogni caso occorrerebbe costruire una classe ad och, per economizzare il tempo di elaborazione. <IMG SRC="images/forum/icons/icon24.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: acarus il 16-05-2003 18:59 ]
Che cos'è il genio....? E' colpo d'occhio, intuizione e velocità d'esecuzione!
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Scusa Biagio, mi sono sbagliato; è come dici tu, si arriva fino a + di 2 mld. Sorry!
<BR>
<BR>P.S.:ank\'io ne ho fatto uno x scomporre i numeri, ma lo fa in meno di 6 sec. se vuoi te lo mando (la mia e-mail è <a href=\"mailto:eu.dima@tin.it\" target=\"_new\">eu.dima@tin.it</a>); tanto che ci sei dammi i tuoi 2 prog.
<BR>
<BR>P.P.S.: x Acarus non si scrive ad och ma ad hoc e vine dal latino<BR><BR>[ Questo Messaggio è stato Modificato da: Simo_the_wolf il 16-05-2003 21:12 ]
Alex85
Messaggi: 197
Iscritto il: 01 gen 1970, 01:00
Località: Roma eur
Contatta:

Messaggio da Alex85 »

c\'è un piccolo problema per creare i numeri come stringa: come mettere la fine della stringa? ad esempio lo 0 non va bene, perchè 2^5 + 0*2^8 + 33*2^16 ad esempio verrebbe mal interpretato, interpretato come soltanto 2^5.
<BR>magari far sì che i primi 7 bit servano a indicare il numero, e il settimo funga da eventuale bit di fine stringa <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>alex
acarus
Messaggi: 106
Iscritto il: 01 gen 1970, 01:00
Località: Molto lontano ...

Messaggio da acarus »

<BR>P.P.S.: x Acarus non si scrive ad och ma ad hoc e vine dal latino
<BR>
<BR>Mai successo di scambiare due lettere digitando velocemente sulla tastiera?
Che cos'è il genio....? E' colpo d'occhio, intuizione e velocità d'esecuzione!
lucianorossi
Messaggi: 195
Iscritto il: 01 gen 1970, 01:00
Località: Livorno
Contatta:

Messaggio da lucianorossi »

grazie delle vostre spiegazioni, ma vedete, io non ne capisco molto <IMG SRC="images/forum/icons/icon_eek.gif">
<BR>Come si fanno tutte queste cose?
afullo
Messaggi: 945
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-05-16 21:07, Simo_the_wolf wrote:
<BR>Scusa Biagio, mi sono sbagliato; è come dici tu, si arriva fino a + di 2 mld. Sorry!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>credo si arrivi fino a 2^31-1
Iscritto all'OliForum dalla gara del 19/02/2003.

Cesenatico - 2003 : 9 punti - menzione (193°) | 2004 : 19 - argento (33°) | 2005 : 21 - bronzo (69°) | 2006 : 25 - argento (20°)
Squadra B. Pascal (Giaveno) - 2005: 6° | 2006: 8°
Cattolica - 2006: 4°
Bocconi GP - 2009: 29° | 2010: 44° | 2012: 17° | 2013: 22° | 2014: 17° | 2015: 38° | 2016: 23° | 2017: 4° | 2018: 14° | 2019: 7° | 2021 (par): 8° | 2022: 6° | 2023: 5°

Ex allenatore di: Cattaneo, Copernico, Ferraris (TO), Newton (Chivasso), Pascal (Giaveno).
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Infatti 2^31-1=2\'147\'483\'647
Bloccato