Numeri primi con Visual Basic

[Karistotele1]

Ho un numero intero positivo. Come faccio a stabilire se è un numero primo? Naturalmente il numero 1 deve essere escluso.

[infinito1971]

Ciao Karistotele,
il tuo problema è un classico: in quanto tale è stato ampiamente studiato anche da grandi matematici; per cui, a prescindere dal linguaggio con cui vuoi tentarne un'implementazione, ti consiglio di documentarti (ad esempio qui) per capire quantomeno quali sono i principali metodi di approccio al problema.


Un saluto,
infinito1971

[Karistotele1]

Ho approcciato il problema in diversi modi. Il più versatile mi sembrava concettualmente il crivello di Eratostene. Però con grandi numeri (di tipo long) mi sono accorto di un antieconomicità del sistema, visto che un vettore di numeri primi si dilata sempre più negli intervalli più grandi.
In ogni caso con due variabili, una riservata al NUMERO PRIMO (N) e considerando il resto di N/C .... C inizianalizzata a 1 all'interno di un ciclo for next, se il resto è diverso da zero e (AND) C minore di radice quadarata di N, IL NUMERO N é primo.
Non saprei come impostare quanto segnalato da te in WKP: "Il test di primalità basilare, che si basa sulla definizione stessa di numero primo, è il seguente: dato un numero di input n, si verifichi se esiste un intero m compreso tra 2 e n − 1 tale da dividere n. Se n è divisibile per un qualunque m allora n è composto, altrimenti è primo. Il limite n-1 può essere abbassato a \sqrt{n}, in quanto se tutti i fattori fossero maggiori di questo valore, il loro prodotto sarebbe necessariamente maggiore di n, il che è assurdo"
Puoi darmi due righe di codice per una function? Grazie

[infinito1971]

Ciao Karistotele,
se hai letto con attenzione quanto contenuto nella pagina del link suggerito nel precedente topic, avrai senz'altro notato che, dal punto di vista computazionale, uno dei migliori approcci è quello costituito dall'utilizzo dell'algoritmo AKS.
Nella stessa pagina è contenuto sia il link alla pagina wikipedia dove è descritto brevemente a cosa serve l'algoritmo (con un link al documento originale che lo descrive), sia il link ad un'implementazione Java dello stesso.
Nel caso, invece, che tu non voglia utilizzare il suddetto algoritmo ma voglia solo vedere qualche snippet implementativo in vb di qualche test di primalità, non posso che consigliarti di visionare quanto presente qui.
Spero di esserti stato d'aiuto.


Un saluto,
infinito1971

[Karistotele1]

Le nuove frontiere della computazione probabilistica sono molto interessanti e mi appassionano ma io volevo rimanere per questa volta sul "classico" e su quanto hai gentilmente linkato a proposito di VB non trovo situazioni particolarmente stimolanti. Puoi dirmi cosa pensi di questa?

Codice: Seleziona tutto

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

Grazie

P.S. Naturalmente non considero come numero primo il numero 1

[infinito1971]

Ciao Karistotele,
scusami per il ritardo con cui ti rispondo ma non volendo rispondere in modo frettoloso alla tua domanda ho preferito attendere un pò per trovare il giusto tempo da dedicare alla risposta che merita.
Per farlo, non ho trovato parole migliori di quelle riportate in questo articolo che ti riporto quasi alla lettera: quello che proponi non è altro che un'implementazione in VB6 del più antico e semplice test di primalità, ossia quello della "divisione per tentativi", che consiste nell'applicare direttamente la definizione di numero primo: si prova a dividere il numero N per tutti i numeri minori di N: se nessuno di questi lo divide, allora il numero è primo con un semplice miglioramento limitando i tentativi di divisione ai numeri primi minori di . Sebbene molto semplice da descrivere e da implementare su un calcolatore, tale metodo è poco usato nella pratica, perché richiede tempi di calcolo che aumentano esponenzialmente rispetto al numero delle cifre di N. Esso tuttavia fornisce anche i suoi fattori primi (ed è quindi un algoritmo di fattorizzazione): questo non succede nel caso di algoritmi più sofisticati, che riescono a stabilire se un numero non è primo anche non determinando alcun divisore non banale.
Spero che tale risposta ti soddisfi e spero di ritrovarti nuovamente nei forum di pc-facile!


Un saluto,
infinito1971