Valutazione 4.87/ 5 (100.00%) 5838 voti

Condividi:        

La solitudine dei numeri primi

Vuoi potenziare i tuoi documenti Word? Non sai come si fa una macro in Excel? Devi creare una presentazione in PowerPoint?
Oppure sei passato a OpenOffice e non sei sicuro di come lavorare al meglio?

Moderatori: Anthony47, Flash30005

La solitudine dei numeri primi

Postdi Karistotele1 » 22/01/13 07:21

Ciao,
Vorsei trovare con una function se un intero (long) positivo è un numero primo. Concettualmente il crivello di Eratostene mi sembra antieconomico.
Ciao da K
Karistotele1
Utente Junior
 
Post: 10
Iscritto il: 21/01/13 07:11
Località: Padova

Sponsor
 

Re: La solitudine dei numeri primi

Postdi Flash30005 » 22/01/13 08:17

Qualcosa di più semplice del crivello di Eratostene è questo programma in Java
http://www.marcocavicchioli.it/numeri%20primi/numeri_primi_generatore.html

Ciao
Flash
Win7 + Office 2010 Ita
"Fotografica" al servizio dell'immagine

Ottime opportunità di lavoro (part-time o full-time) con guadagni immediati. Info in MP
Avatar utente
Flash30005
Moderatore
 
Post: 8460
Iscritto il: 27/09/07 11:44
Località: Roma +o-

Re: La solitudine dei numeri primi

Postdi wallace&gromit » 22/01/13 08:33

ciao Karistotele,
..oppure forse ti può andare bene questa funzione
Codice: Seleziona tutto
Function numprimi(num)
numprimi = "primo"
For i = 2 To num - 1
If Int(num / i) = num / i Then
numprimi = "multiplo"
End If
Next i
End Function


P.S. nella mia ignoranza non so cos'è il crivello di Eratostene, magari è proprio questo (però è veloce, quindi "economico")
P.S. 2 ma sei lo stesso Karistotele che già frequentava il forum o siete in due e aumentate come i numeri primi?
stato 2014: Office2003/2013 su win7
Avatar utente
wallace&gromit
Utente Senior
 
Post: 1421
Iscritto il: 16/01/12 14:21

Re: La solitudine dei numeri primi

Postdi Anthony47 » 22/01/13 10:01

Bentornato a karistotele.
W&g, la tua function e' una trappola: prova a usarla su 11113, 55001, 99901, e poi grande salto fino a 1234517.

Un certo miglioramento si otterra' modificando in
Codice: Seleziona tutto
Function numprimi(num As Long) As Boolean
numprimi = True
For I = 2 To num / 2
    If Int(num / I) = num / I Then
        numprimi = False
        Exit Function
    End If
Next I
End Function

Le modifiche sono il ciclo For I=2 to num/2 e la Exit Function intermedia.

Comunque questo e' solo un cerotto su un problema ben piu' grande, considerando che il tipo Long puo' contenere un valore alto fino a 2.147.483.647 (quindi 2000 volte superiore al max numero che ti ho suggerito di testare prima), e in questo range ci sono ben oltre 50 milioni di numeri primi.
Vedro' se riesco ad approfondire piu' tardi.

Ciao a tutti
Anthony
Win7 + Office 2010 Ita; Win 7 + Office 2013 Ita
Xp + Office 2003 Ita
E voi cosa usate? (per istruzioni vedere viewtopic.php?f=26&t=97449)
Avatar utente
Anthony47
Moderatore
 
Post: 13895
Iscritto il: 21/03/06 16:03
Località: Ivrea

Re: La solitudine dei numeri primi

Postdi Anthony47 » 22/01/13 16:20

La macro del messaggio precedente puo' essere ulteriormente modificata considerando che il ciclo di verifica, gia' accorciato a For I = 2 To num / 2 puo' essere ulteriormente ridotto a
Codice: Seleziona tutto
For I = 2 To (num ^ (1 / 2))  'fino a radice quadra NUM


Il tempo di esecuzione risulta ulteriormente ridotto: se prima era di circa 0,1 sec ogni Milione (quindi numeri primi dell' ordine di 32.000.000 richiedevano circa 3,1 sec) adesso risulta ridotto di un fattore di almeno 1000 (collaudato fino a 982.451.653, con tempi inferiori a 0,02 sec)

Non so se questo risultato puo' ritenersi sufficiente per karistotele.

Ciao
Anthony
Win7 + Office 2010 Ita; Win 7 + Office 2013 Ita
Xp + Office 2003 Ita
E voi cosa usate? (per istruzioni vedere viewtopic.php?f=26&t=97449)
Avatar utente
Anthony47
Moderatore
 
Post: 13895
Iscritto il: 21/03/06 16:03
Località: Ivrea

Re: La solitudine dei numeri primi

Postdi Karistotele1 » 22/01/13 17:22

Ciao Anthony, piacere di reincontrarti.
La soluzione infatti (si evince dal crivello di eratostene) è quella di utilizzare la radice quadra. Nel caso da te citato bisognerebbe ciclare circa un miliardo di volte con la divisione per due , invece con la radice quadra circa 46.000 volte.
E' buono ed utile, in effetti quì ero arrivato. Occorre naturalmente precisare che un numero non primo è ovviamento composto ed esso, ha accertato a suo tempo, mi sembra Eulero, è semplicemente il prodotto di due numeri primi. Non c'è quindi bisogno di fare tutte le operazioni diviso 2 ma basta considerare la radice tenendo presente che un numero composto è il prodotto di due numeri primi. Non voglio allungarmi sulla matematica. Cercavo in effetti di accorciare ancora usando un eventuale altro algoritmo che non riesco a trovare. In ogni caso cotanto mi è lo stesso utile e ringrazio per l'accoglienza.
Ciao da K
Karistotele1
Utente Junior
 
Post: 10
Iscritto il: 21/01/13 07:11
Località: Padova

Re: La solitudine dei numeri primi

Postdi Anthony47 » 23/01/13 00:53

Volendo mettere i puntini sulle u, la macro iniziale richiedeva di ciclare sempre N-1 volte; la versione modificata di stamattina ciclava "fino a N/2 volte", l' ultima versione cicla "fino a RadiceQuadrata di N". La modifica da N/2 a Radical-N mi e' stata evidente leggendo la descrizione del "crivello di Eratostene" (che e' un metodo per estrarre tutti i Primi di un intervallo): avendo testato la divisibilita' fino a Radice-N, divisori piu' alti sono ancora possibili ma in questo caso darebbe luogo a un "quoto" piu' basso di Radice-N, cosa che e' stata gia' esclusa dal fatto che siamo andati avanti nel test.
Non ho nessuna preparazione scientifica per invece capire e applicare il metodo AKS

Superflua, ai fini dei ragionamenti pratici, anche la precisazione che un numero "non primo" puo' risultare dal prodotto di 2, 3, 4,... , N numeri primi.

Ciao a tutti.
Anthony
Win7 + Office 2010 Ita; Win 7 + Office 2013 Ita
Xp + Office 2003 Ita
E voi cosa usate? (per istruzioni vedere viewtopic.php?f=26&t=97449)
Avatar utente
Anthony47
Moderatore
 
Post: 13895
Iscritto il: 21/03/06 16:03
Località: Ivrea


Torna a Applicazioni Office Windows


Topic correlati a "La solitudine dei numeri primi":


Chi c’è in linea

Visitano il forum: Nessuno e 15 ospiti