[C]Long double

[L4ky]

Ciao a tutti. Ho bisogno di fare un programma che generi numeri primi all'infinito. Siccome c'è una sorta di "gara" in classe vorrei ovviamente vincerla. Per cui il numero dovrà essere sufficientemente grande, e ovviamente una variabile intera non è sufficiente.
Per cui ho pensato alle long double, che sono grandi 12 Byte = 96 bit.
Dovrebbe bastare.
Il problema è che per la verifica dei numeri primi non si può usare il modulo, da errore.
Come faccio a verificare se il numero in long double è primo??

[Gimli[2BV!2B]]

Non è meglio un long long, magari pure unsigned?

[L4ky]

;34985745']Non è meglio un long long, magari pure unsigned?

Unsigned da errore
Long long è meglio.
Consigli sulla verifica numeri primi?

[clockover]

Unsigned da errore
Long long è meglio.
Consigli sulla verifica numeri primi?

Fa una ricerca qui in programmazione... ricordo una discussione analoga un po di tempo fa

[Supdario]

Ciao a tutti. Ho bisogno di fare un programma che generi numeri primi all'infinito. Siccome c'è una sorta di "gara" in classe vorrei ovviamente vincerla. Per cui il numero dovrà essere sufficientemente grande, e ovviamente una variabile intera non è sufficiente.
Per cui ho pensato alle long double, che sono grandi 12 Byte = 96 bit.
Dovrebbe bastare.
Il problema è che per la verifica dei numeri primi non si può usare il modulo, da errore.
Come faccio a verificare se il numero in long double è primo??

Un long double ha la dimensione di 80 bit, e tuttavia non è supportato da tutti i compilatori (anzi, ormai sta diventando una feature deprecata in tutti i compilatori dato che ormai tutti i calcoli FPU vengono eseguiti a 64 bit, anche per via delle istruzioni SSE che permettono al massimo numeri di 64 bit).

Come ti hanno detto, un unsigned long long può fare al caso tuo. :D

Immagino che tu conosca già l'algoritmo per controllare se un numero è primo, ma se il tuo obiettivo è quello di listare i numeri primi, controllare tutti i numeri uno ad uno potrebbe diventare un po' lento. :D
Una soluzione potrebbe essere quella di usare un vettore dinamico (o una lista) in cui memorizzi tutte le soluzioni precedenti (i fattori), e per controllare se un numero è primo parti dalle soluzioni precedenti e ne trovi di nuove, aggiungendole alla lista.

[L4ky]

Allora sono andato avanti.
Per ora uso unsigned long long int (che a quanto pare è di 64bit), cosi posso usare il modulo %.
I risultati li salvo su file, e quando riapro il file automaticamente carica l ultimo numero salvato! :D


Se volessi qualcosa di più grande di 64bit come si può fare?

[Supdario]

Non credo che tu riesca ad arrivare ad un numero primo che sia maggiore di 18446744073709551616 (2^64 - 1).
In ogni caso per avere più di 64 bit ti tocca usare numeri a precisione arbitraria (i cosiddetti BigNum). Il modo più semplice per farlo è quello di appoggiarsi a librerie esterne che puoi reperire facilmente su internet.

[L4ky]

Ho fatto il programma con i long double e funziona.
Ora ho solo un problema. Quando i numeri diventeranno mooolto grandi, il cout di default mi visualizzerà qualche cifra seguita da un esponente. Come faccio a evitare di visualizzare l'esponente e vedere il numero per intero?

[Supdario]

Ho fatto il programma con i long double e funziona.
Ora ho solo un problema. Quando i numeri diventeranno mooolto grandi, il cout di default mi visualizzerà qualche cifra seguita da un esponente. Come faccio a evitare di visualizzare l'esponente e vedere il numero per intero?

Non puoi, perché per loro natura i numeri a virgola mobile vengono memorizzati in notazione esponenziale, quindi quando diventano grossi iniziano a perdere precisione e certi numeri non possono essere rappresentati.
Volendo puoi forzare la visualizzazione, ma non vedrai altro che una fila di 0. Ti faccio un esempio:
2+1 = 3 (questo lo riesce a rappresentare, visto che è un numero piccolo)
20+1 = 21 (idem)
...
2000000000000000000000000000000000+1 = 2000000000000000000000000000000000 (in questo caso non può farci niente, perché la precisione non è abbastanza elevata da permettere di memorizzare quell'1 meno significativo).

Proprio per questo motivo ti sconsiglierei di usare i double, visto che il loro range di numeri è elevato, ma non è distribuito uniformemente tra tutti i numeri.

[:.Blizzard.:]

Consigli sulla verifica numeri primi?

Il test di primalità non è per nulla banale, e gioca un ruolo molto importante nell'ambito della crittografia.

Puoi ricorrere a test non deterministici -quindi più test fai più aumenti la certezza riguardo al fatto che il numero sia primo- e tutti si basano su un concetto molto semplice: se un numero è primo, gode di determinate proprietà.

Matematicamente invece beh, è un altro discorso :D

Dai un occhio qua, trovi i più importanti: Soloway-Strassen, Miller-Rabin e il Test di Fermat:

http://www.dti.unimi.it/citrini/MD/SitoG-M/sol-stras.htm