Numeri primi

Question

Ciao,

Vorrei con una function stabilire se un numero positivo di tipo long è primo oppure no.

Vorrei evitare il ragionamento del crivello di Eratostene che mi sembra antieconomico. Grazie

Answer 1

Ciao Mauro, speravo comunque in un diverso algoritmo

<cut>           

L'algoritmo è comunque valido. L'ho testato anche in vb.net dove un intero può arrivare a:

9.223.372.036.854.775.807

Ho chiesto se questo numero è primo: 9.223.372.036.850.770.027 (e lo è).

Il tutto ha richiesto circa 45/50 secondi con un processore i7 3612QM. Considera il numero di operazioni necessarie (oltre tre miliardi).

Scarica TestPrimi.zip da qui se vuoi provare:

https://skydrive.live.com/?cid=0361684D94BB851A#cid=0361684D94BB851A&id=361684D94BB851A%21281

Scritto, al volo, in vb.net

Answer 2

Ciao Santo_Caristia,

grazie ma non serviva.

Ti ho segnalato il thread non perché ti fermassi al titolo ma per alcune cose riguardanti i numeri primi che lì sono state discusse. ;-)

Answer 3

Ciao Mauro, speravo comunque in un diverso algoritmo. La tua seconda in effetti è precisamente quella che ho usato io. Grazie in ogni caso… In effetti la “disputa” tale non è. E’ una necessità considerare il numero 1 non primo poiché diventerebbero incongruenti una serie di teoremi quali la unicità della fattorizzazione, il teorema fondamentale dell’aritmetica ed altri in cui è meglio che io non mi avventuri. Per definire un numero primo a scuola ci hanno sempre insegnato che un numero è primo se è divisibile per se stesso e uno. Da tempo si preferisce dire: Un intero positivo n si dice primo se ha esattamente due divisori positivi.

Grazie Mauro.

Grazie anche a Maurizio per l’interesse ma …. per brevità [… da Wikipedia]: Untest di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo. Non va confuso con un algoritmo di fattorizzazione, che invece ha lo scopo di determinare i fattori primi di un numero.

Answer 4

Ciao,

Vorrei con una function stabilire se un numero positivo di tipo long è primo oppure no.

Vorrei evitare il ragionamento del crivello di Eratostene che mi sembra antieconomico. Grazie

Il crivello è l'unico che ti dia una certezza assoluta nei limiti che hai esposto:

Public Function f(ByVal lng As Long) As Boolean

    Dim l As Long

    f = True

    For l = 2 To Sqr(lng) + 1

        If lng Mod l = 0 And lng <> l Then

                f = false

                Exit Function

        End If

    Next

End Function

Nei miei pc il tempo per calcolare se questo numero è primo (e lo è): 1999999927 è nell'ordine di un attimo. Puoi aggiunfgere un If per avere False nel caso di cella vuota o pari a zero e come forse sai c'è una disputa sul fatto che 1 sia o meno un numero primo. Nel caso:

Public Function f(ByVal lng As Long) As Boolean

    Dim l As Long

    f = True

    If lng < 2 Then

        f = False

        Exit Function

    End If

    For l = 2 To Sqr(lng) + 1

         If lng Mod l = 0 And lng <> l Then

                 f = False

                 Exit Function

         End If

     Next

End Function

Answer 5

Ciao Santo_Caristia,

forse ti potrà interessare questa recente discussione in mpioe:

• Scomposizione in fattori primi

HTH