Pagina 1 di 2
Il primo che viene prima
Inviato: 14 lug 2009, 23:25
da Enrico Leon
Mathematica ha implementata la seguente funzione:
NextPrime[n] che restituisce il numero primo immediatamente successivo ad n.
In quale modo è possibile trovare il numero primo immediatamente precedente ad n?
Re: Il primo che viene prima
Inviato: 14 lug 2009, 23:35
da ndp15
Mi verrebbe da dire:"Cercando tutti i primi minori di n e prendendo il maggiore" ma mi sa che non ho ben capito la richiesta
Inviato: 14 lug 2009, 23:51
da exodd
io di solito, in C, considero (in successione) n, n-1, n-2,...,2 ed ogni numero lo divido per tutti i successivi: appena ne trovo uno che non è divisibile per tutti i successivi, lo scrive
in formule:
Codice: Seleziona tutto
while (n>1)
{
a=n-1;
while (a>1)
{
r=n%a;
if (r==0)
{
break;
}
if (a==2)
{
printf ("%d\n", n);
}
a=a-1;
}
if (a==1)
{
break;
}
n=n-1;
}
Inviato: 14 lug 2009, 23:53
da Tibor Gallai
Un modo un po' più efficiente è iterare NextPrime su n/2, fino ad ottenere n o più.
Perché n/2? Perché esiste un primo tra n/2 e n, per il teorema di Bertrand-Chebyshev.
Esempio con n=37:
n/2 = 18.5
NextPrime(18.5) = 19
NextPrime(19) = 23
NextPrime(23) = 29
NextPrime(29) = 31
NextPrime(31) = 37
Quindi la risposta è 31.
@ exodd: al solito, calcolare una radice quadrata è più efficiente che fare O(n) divisioni...
Inviato: 14 lug 2009, 23:58
da julio14
Non si fa prima a trovare il nextprime di n e poi procedere all'indietro finché non ne si trova uno minore?
Inviato: 14 lug 2009, 23:59
da Tibor Gallai
julio14 ha scritto:Non si fa prima a trovare il nextprime di n e poi procedere all'indietro finché non ne si trova uno minore?
A cosa serve trovare il nextprime di n?
Inviato: 15 lug 2009, 00:01
da Enrico Leon
No, no, no... Perché cercare disgrazie?? Molto, molto, ma molto più semplice........... In una sola riga.........
Inviato: 15 lug 2009, 00:01
da julio14
Stavo per rispondere "perché anche n potrebbe essere primo" ma poi mi sono accorto della cavolata... se cerchiamo il minore stretto basta minore di n. Anche perché se era minore largo bastava mettere minore largo nell'algoritmo... scusate i deliri di mezzanotte
Inviato: 15 lug 2009, 00:04
da Tibor Gallai
Enrico Leon ha scritto:No, no, no... Perché cercare disgrazie?? Molto, molto, ma molto più semplice........... In una sola riga.........
Ma non ho capito, cerchi una formula di Mathematica, un programma in un linguaggio qualsiasi, un algoritmo computazionalmente ottimo...?? Cosa?
Tra l'altro, MathWorld dice:
"The previous prime function was implemented in versions of Mathematica prior to 6 as PreviousPrime[n] (after loading the package NumberTheory`NumberTheoryFunctions)."
E' questa la risposta che volevi?
Inviato: 15 lug 2009, 00:09
da Enrico Leon
Solamente sfruttando la funzione NextPrime[n] e aggiungendo qualche altra cosa "elementare" trovare il numero primo immediatamente precedente ad n. Io so la risposta, non è che sto cercando un'altra funzione che non conosco...
Inviato: 15 lug 2009, 00:12
da Tibor Gallai
Dipende da come tratta i numeri primi (non conosco Mathematica!), ma -NextPrime[-n] potrebbe andare?
Inviato: 15 lug 2009, 00:14
da Enrico Leon
Esatto! Infatti la "vera" definizione di numeri primi comprende anche i numeri negativi!
Inviato: 15 lug 2009, 00:25
da SkZ
moltiplicazioni e addizioni sono le operazioni piu' elementari che richiedono in pratica nulla (un paio di cicli). La divisione puo' richiedere anche 30-100 cicli.
volendo
http://reference.wolfram.com/mathematic ... Prime.html
anche piu' semplice
NextPrime[n,-1]
Inviato: 15 lug 2009, 14:22
da Enrico Leon
Certo, ma bisognava farlo senza sapere che si poteva inserire anche un secondo argomento!
Comunque... Che cosa si intende esattamente per "ciclo"?
Inviato: 15 lug 2009, 15:59
da Agi_90
Enrico Leon ha scritto:Che cosa si intende esattamente per "ciclo"?
Sostanzialmente il processore riceve in maniera periodica un impulso di corrente; ad ogni impulso il processore compie un numero di operazioni, questo è un ciclo.