[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]

Originariamente inviato da Gimli[2BV!2B]

Non è meglio un long long, magari pure unsigned?

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

[clockover]

Originariamente inviato da L4ky

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]

Originariamente inviato da 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??

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.

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.
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!


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]

Originariamente inviato da 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?

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.:]

Originariamente inviato da L4ky

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

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

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