Il primo che viene prima

Giochini matematici elementari ma non olimpici.
Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Il primo che viene prima

Messaggio da Enrico Leon » 14 lug 2009, 23:25

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?

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Il primo che viene prima

Messaggio da ndp15 » 14 lug 2009, 23:35

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 :roll:

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 14 lug 2009, 23:51

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;
}
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 14 lug 2009, 23:53

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...
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]

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 14 lug 2009, 23:58

Non si fa prima a trovare il nextprime di n e poi procedere all'indietro finché non ne si trova uno minore?

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 14 lug 2009, 23:59

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?
[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]

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 15 lug 2009, 00:01

No, no, no... Perché cercare disgrazie?? Molto, molto, ma molto più semplice........... In una sola riga.........

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 15 lug 2009, 00:01

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.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 15 lug 2009, 00:04

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?
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]

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 15 lug 2009, 00:09

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...

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 15 lug 2009, 00:12

Dipende da come tratta i numeri primi (non conosco Mathematica!), ma -NextPrime[-n] potrebbe andare?
[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]

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 15 lug 2009, 00:14

Esatto! Infatti la "vera" definizione di numeri primi comprende anche i numeri negativi!

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 15 lug 2009, 00:25

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]
:wink:
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

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 15 lug 2009, 14:22

Certo, ma bisognava farlo senza sapere che si poteva inserire anche un secondo argomento! :wink: Comunque... Che cosa si intende esattamente per "ciclo"?

Avatar utente
Agi_90
Messaggi: 331
Iscritto il: 21 mar 2007, 22:35
Località: Catania
Contatta:

Messaggio da Agi_90 » 15 lug 2009, 15:59

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.
[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?"

Rispondi