Il primo che viene prima
-
- Messaggi: 237
- Iscritto il: 24 nov 2008, 18:08
- Località: Gorizia
Il primo che viene prima
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?
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
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
- exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
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:
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;
}
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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...
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...
Ultima modifica di Tibor Gallai il 15 lug 2009, 00:14, modificato 2 volte in totale.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
A cosa serve trovare il nextprime di n?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?
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
- Messaggi: 237
- Iscritto il: 24 nov 2008, 18:08
- Località: Gorizia
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
Ultima modifica di julio14 il 15 lug 2009, 00:06, modificato 1 volta in totale.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Ma non ho capito, cerchi una formula di Mathematica, un programma in un linguaggio qualsiasi, un algoritmo computazionalmente ottimo...?? Cosa?Enrico Leon ha scritto:No, no, no... Perché cercare disgrazie?? Molto, molto, ma molto più semplice........... In una sola riga.........
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?
Ultima modifica di Tibor Gallai il 15 lug 2009, 00:09, modificato 1 volta in totale.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
- Messaggi: 237
- Iscritto il: 24 nov 2008, 18:08
- Località: Gorizia
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
-
- Messaggi: 237
- Iscritto il: 24 nov 2008, 18:08
- Località: Gorizia
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]
volendo
http://reference.wolfram.com/mathematic ... Prime.html
anche piu' semplice
NextPrime[n,-1]
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
-
- Messaggi: 237
- Iscritto il: 24 nov 2008, 18:08
- Località: Gorizia
Sostanzialmente il processore riceve in maniera periodica un impulso di corrente; ad ogni impulso il processore compie un numero di operazioni, questo è un ciclo.Enrico Leon ha scritto:Che cosa si intende esattamente per "ciclo"?
[url]http://www.agiblog.it/[/url]
Io abolirei e bannerei a vita tutti quelli che postano cose del tipo "ciao io ho fatto questo problema e ho risolto così, non sono strafigo?"
Io abolirei e bannerei a vita tutti quelli che postano cose del tipo "ciao io ho fatto questo problema e ho risolto così, non sono strafigo?"