Numeri primi e crivello di eratostene

[gamer07]

Salve a tutti,

ho un dubbio esistenziale, premetto che ho già cercato in giro per la rete

Non riesco a capire perchè, nell'ottimizzazione dell'algoritmo del crivello di Eratostene , basta fermarsi alla radice quadrata dell'n dato in input ( insomma del numero che indica il limite superiore fin dove cercare i numeri primi).

Mi ero fermato ad n/2 .. Ma perchè la radice quadrata mi assicura che non ci sono multipli altri numeri non primi ?
Come si può dimostrare questa cosa? Vorrei capire il perchè è così.

NB: siate elementari e chiari nella spiegazione(please)!
Grazie!

[axpgn]

Guarda qui

[gamer07]

intanto ti ringrazio!
Mi sto sforzando per capire ... non mi è chiarissimo, scusami

Un numero è composto sempre da due fattori di cui uno è primo ?!
faccio fatica a capire ancora perchè nel crivello dobbiamo fermarci ai multipli della radice quadrata di un dato n e oltre praticaamente non avvengono più cancellazioni... Il fatto che non riesco a fare mio questo concetto è però dovuto al fatto che non mi è chiaro il passaggio precedente..

Poniamo di avere un intero n, la sua radice n−−√ ed una coppia (p,q) di divisori di n=p⋅q, diversi fra loro e di cui almeno uno minore (o uguale) a n−−√ (almeno uno esiste sempre, pensa a 1 come divisore).
Quindi pn−−√.

potresti farmi esempi numerici con numeri a caso maggiori di 1 e poi con 1 come divisore? .. sono un pò confuso.. scusami!

[mgrau]

Ci provo anch'io...
se un numero N non è primo, deve essere formato da almeno 2 fattori, n1 e n2, con N = n1*n2
Supponiamo che sia n1 il puù piccolo dei due, o al più uguale a n2. (Se fosse maggiore, cambiamo i nomi...)
Ora, $N = sqrt(N)*sqrt(N)$, e questo è l'unico modo per scomporre N in due fattori uguali (in genere non interi, per cui non è questa la scomposizione che cerchiamo)
In tutti gli altri casi, i due fattori sono, uno minore di $sqrt(N)$, l'altro maggiore.
Quindi, se consideriamo i candidati partendo dai numeri piccoli e crescendo, il primo che incontreremo sarà n1, e lo incontreremo prima di $sqrt(N)$; se invece non lo incontriamo, vuol dire che n1 non c'è, per cui ci possiamo fermare.

[axpgn]

Un numero naturale può sempre essere scomposto in un prodotto di due numeri naturali, anche se è primo; per esempio $31=1*31$.
Se è composto, ovviamente ce ne sono altre di scomposizioni, come $30=1*30=2*15=3*10=5*6$.
Quindi i divisori (primi o no) di $n$ vanno sempre a coppie (tranne quando $n$ è un quadrato perfetto, in tal caso c'è un divisore "single" come $100=10*10$).
Ci siamo fin qui?
Si può dimostrare (quello che ho fatto nel post che ho citato) che in queste coppie di divisori di $n$, uno è sempre minore (o uguale) di $sqrt(n)$, l'altro è sempre maggiore (o uguale) di $sqrt(n)$.
Nella dimostrazione, quale punto non ti è chiaro?

Cordialmente, Alex

[gamer07]

Grazie ragazzi, ringrazio entrambi per essere intervenuti e per aver provato ad aiutarmi .

La spiegazione mi è chiara e anche la dimostrazione che altro non fa che dire praticamente che un fattore è minore e l'altro è maggiore.

Ma dove faccio fatica è il passo successivo.
Esattamente quando dici :

Quindi, se consideriamo i candidati partendo dai numeri piccoli e crescendo, il primo che incontreremo sarà n1, e lo incontreremo prima di N−−√; se invece non lo incontriamo, vuol dire che n1 non c'è, per cui ci possiamo fermare.

Ecco, perchè possiamo fermarci ?
Cioè non riesco a capire perchè partendo da un fattore N1 non troveremo altri numeri da cancellare .
Capiamoci, se lo svolgo a mano o con algoritmo funziona. Ma io è il perchè che non capisco..

Provo a scrivere cose "assurde" proprio per farvi capire dove mi inceppo:

un certo numero naturale a = p * q.
ora sappiamo che p e q sono uno minore e l'altro maggiore di $ sqrt a $. Perfetto.
Ora perchè trovato p e tutti i suoi multipli so con certezza che non troverò altri numeri da cancellare fino ad a ?
perchè non esisterà una p : p * q' = b; [size=120]??[/size]

Perdonatemi eh, sarò di coccio ma se faccio fatica a capire questo step, faccio fatica

[mgrau]

Scusa, ma il problema quale è? Non si tratta di capire se N è, o non è, primo?
Allora, se trovi il primo fattore, hai finito: non è primo. Cancelli N (non p). Volendo, a questo punto, puoi trovare anche gli altri fattori: ma è un problema diverso. E comunque, ti conviene calcolare M = N/p, e ripartire da M.
Se invece non lo trovi, è primo. E' inutile che vai avanti, se hai trovato che non c'è un fattore minore di $sqrt(N)$, cosa vorresti cercare?

[gamer07]

"mgrau":Scusa, ma il problema quale è? Non si tratta di capire se N è, o non è, primo?
Allora, se trovi il primo fattore, hai finito: non è primo. Cancelli N (non p). Volendo, a questo punto, puoi trovare anche gli altri fattori: ma è un problema diverso. E comunque, ti conviene calcolare M = N/p, e ripartire da M.
Se invece non lo trovi, è primo. E' inutile che vai avanti, se hai trovato che non c'è un fattore minore di $sqrt(N)$, cosa vorresti cercare?

si parla del crivello di Eratostene. Cmq non m'interessa sapere se N è primo o non è primo.
Mi interessa capire come funziona la cancellazione dei multipli di fattori primi nello specifico perchè ci si ferma a $ sqrt n $ che è la cosa ce non riesco a capire.
Cmq non ho capito cosa vuoi dire con M = N/p ...

Io non riesco a convincermi del fatto che faccio un esempio stupido

n = 28 $ sqrt 28 = 5, ...
2 è primo ok, cancello tutti i suoi multipli -> perfetto
3 è primo ok, cancello tutti i suoi multipli -> perfetto
5 è primo ok, cancello tutti i suoi multipli -> perfetto
7 è primo ok, non c'è bisogno che cancello i suoi multipli qui impazzisco
11 è primo ok , non c'è bisogno che callo i suoi mulitpli
etc...

perchè non può accadere che trovo un numero che non è stato cancellato >5 ovvero $ sqrt 28 $
cosa indica questa $ sqrt 28 $ .. quando troviamo questo 5,29 cosa significa ?
perchè i multipli dei numeri primi minori della parte intera di $ sqrt 28 $ sono sufficienti per assicurarsi che non esistono altri multipli non primi fino a 28 ?

[igiul1]

Forse perchè sono stati già cancellati in quanto multipli di 2, 3, 5? Che ne dici?

[gamer07]

"igiul":Forse perchè sono stati già cancellati in quanto multipli di 2, 3, 5? Che ne dici?

non credo che questa tua risposta possa aiutarmi a farmi capire perchè basta fermarsi a $ sqrt n $.


prova ad argomentare del perchè $ sqrt n $ rappresenta il limite inferiore per cui i multipli dei primi sono già stati cancellati e non perchè 4 è multiplo di 2 quindi è stato cancellato.

[igiul1]

Se ho ben capito vuoi trovare i numeri primi fino ad un certo numero n.

Poichè le spiegazioni fino ad ora non ti convincono prova a fare qualche esempio scrivendolo a mano.

Scrivi tutti i numeri fino al tuo n. Cerchia la su radice quadrata, anche approssimata, cancella tutti i multipli dei numeri primi fino ad essa ed osserva cosa ti rimane.

[axpgn]

@gamer07
Hai detto che hai capito la dimostrazione ma ho qualche dubbio ...

Dato $n=p*q$ e assodato che $p Per esempio se $n=28$ allora $21$ è multiplo di $7$ e non verrebbe cancellato ... ah, no, perché è multiplo anche di $3$ ... però c'è il $14$ ... ah, no, è multiplo di $2$ e $28$ è multiplo di $4$ ... Coincidenze? Solo un caso?

No. I multipli di $q$ minori di $n$ son tutti quelli che ottengo moltiplicando $q$ per gli interi $m$ compresi tra $2$ e $p$; ora i casi sono due: o $m$ è un primo che abbiamo già trovato e quindi i suoi multipli li abbiamo già cancellati, compresi quindi i multipli di $q$ oppure è composto ma allora è un multiplo di un primo già trovato e vale il discorso appena fatto.
Convinto?

Cordialmente, Alex

[gamer07]

"igiul":Se ho ben capito vuoi trovare i numeri primi fino ad un certo numero n.

Poichè le spiegazioni fino ad ora non ti convincono prova a fare qualche esempio scrivendolo a mano.

Scrivi tutti i numeri fino al tuo n. Cerchia la su radice quadrata, anche approssimata, cancella tutti i multipli dei numeri primi fino ad essa ed osserva cosa ti rimane.

igual perdonami ma è proprio scontato che io abbia provato a mano ... Ma tu mi stai dato una spiegazione pratica...
Se poniamo numeri molto grandi come lo dimostri? a mano mettendoci 2 mesi ?
Non m'interessa ragionare così...

Può essere la cosa più banale al mondo , ma devo capirla e se non la capisco pazienza, impiegherò altro tempo.E' inutile che vuoi forzare la comprensione di qualcosa a qualcuno. Non credo sia l'approccio giusto.
Ti ringrazio cmq per aver tentato di aiutare

[axpgn]

Ma hai letto i miei post?

[igiul1]

Il suggerimento, se così vogliamo chiamarlo ma era anche una provocazione, era per renderti conto che così facendo restavano solo numeri primi, il perchè mi sembra lo abbia spiegato molto bene axpgn nel suo ultimo post.

P.S. Vedo che ti ha già risposto lui ma preferisco lasciare quanto ho scritto.

[gamer07]

"axpgn":Ma hai letto i miei post?

Si Alex e ti ringrazio molto, sia per la qualità sia per le modalità delle tue risposte ...

Purtroppo non sono ancora convinto a pieno.. Non ti ho risposto perchè sto ancora con la mia penna e il mio foglio a dare a capocciate da oggi pomeriggio.

[gamer07]

"axpgn":@gamer07
Hai detto che hai capito la dimostrazione ma ho qualche dubbio ...

Dato $n=p*q$ e assodato che $p Per esempio se $n=28$ allora $21$ è multiplo di $7$ e non verrebbe cancellato ... ah, no, perché è multiplo anche di $3$ ... però c'è il $14$ ... ah, no, è multiplo di $2$ e $28$ è multiplo di $4$ ... Coincidenze? Solo un caso?

sono convintissimo che non sono solo coincidenze, ma deve entrarmi nella testa
Allora il fatto che $n=p*q$ e l'equazione del precedente link dove $ p * q = sqrt n * sqrt n $ bhe sostanzialmente non mi da informazioni aggiuntive se non dirmi che avremo una $p $ e una $q $ rispettivamente minore e maggiore della $sqrt n $
Ma non ha aggiunto informazioni sul fatto del perchè?!?
Che cosa rappresenta la radice quadrata?? Cioè andiamo nelle radice , ditemi perchè i fattori sono cancellati (e non che 4 e 8 sono multipli di 2 quindi li ho già cancellati)

No. I multipli di $q$ minori di $n$ son tutti quelli che ottengo moltiplicando $q$ per gli interi $m$ compresi tra $2$ e $p$; ora i casi sono due: o $m$ è un primo che abbiamo già trovato e quindi i suoi multipli li abbiamo già cancellati, compresi quindi i multipli di $q$ oppure è composto ma allora è un multiplo di un primo già trovato e vale il discorso appena fatto.
Convinto?

Cordialmente, Alex

questa parte si avvicina di più alle mie domande .

prendo di nuovo l'esempio 28 :

28 lo posso scrive soltanto in 3 modi come(in N, come interi) $ n = p*q $ :

$ 2^2 * 7 $
$ 2 * 14 $
$ 1* 28 $

potrebbero esistere dei multipli di $q$ minori di $n$ che non verrebbero cancellati se ci fermiamo ad esaminare i multipli dei primi minori di $sqrt(n)$. Questo è il tuo dubbio, ok?

Nì, perchè ci sono appunto numeri "non" $ q $ come 11 , 13 che sono primi ok, ma non sappiamo se i suoi multipli sono cancellati. Chi ce lo dice ?!
e qui



poi altra cosa

I multipli di $q$ minori di $n$ son tutti quelli che ottengo moltiplicando $q$ per gli interi $m$ compresi tra $2$ e $p$; ora i casi sono due: o $m$ è un primo che abbiamo già trovato e quindi i suoi multipli li abbiamo già cancellati, compresi quindi i multipli di $q$ oppure è composto ma allora è un multiplo di un primo già trovato e vale il discorso appena fatto.
Convinto?

Qui finiamo a domande esistenziali del tipo ... Come si generano i numeri ? ( rido ma mi viene da piangere )

2x1 3x1 4x1 5x1
2x2 3x2 4x2 5x2
2x3 3x3 4x3 5x3
... ... ... ...
... ... ... ...
2x11 3x11 4x11 5x11
2x12 3x12 4x12
2x13 3x13 ....
2x14 3x14 ...

avremo $ a = p x q $ dove la $ p $ sarà 2 , poi avremo altre volte che sarà $ 3 $ etc.. crescendo ..
ora per esempio $ a = 3 * 33 = 99 $ come fate a dire che quando arriveremo ad un $ 11x9 $ è stato già cancellato, non c'è bisogno di ripeterlo ?
Non mi fate leggere la risposta "è divisibile per $ 3 $ " ,quindi già cancellati perchè questo è la cosa pratica che a me non interessa.
Anzi prendende spunto dalla domanda per spiegare e dimostrare che 99 sarà già cancellato

(perdonatemi magari risulto "de coccio" e ripetitivo) ma ... devo capire

[axpgn]

Che fatica ... ... secondo me è sufficiente quello che ho già scritto se lo analizzi ben bene ...

Comunque, proviamo ...

Chiamiamo $n$ il numero limite entro il quale devi fermarti nella ricerca dei tuoi numeri primi. Ok?
Chiamiamo $p$ il più grande intero minore di $sqrt(n)$ (si usa questo simbolo $p=\lfloor sqrt(n)\ \rfloor$ e un paio di esempi sono $5=\lfloor5,291...\rfloor$ e $7=\lfloor7,1\rfloor$)
Tu cosa fai? Ti scorri tutti gli interi da $2$ a $p$, uno alla volta ma saltando quelli eventualmente già cancellati, e per ciascuno di essi, ne cancelli i relativi multipli (fino a $n$ cioè minori o uguali a $n$). Tutto chiaro fin qui?
Dopo aver cancellato anche i multipli di $p$ tu vorresti andare oltre (fino a $n$ in pratica). Giusto?
Inutile.
Perché?
Ripartiamo con la nostra opera di cancellazione dal primo intero maggiore di $sqrt(n)$ non cancellato (quelli maggiori di $sqrt(n)$ cancellati non possono essere numeri primi, concordi? Segnatelo ), che chiameremo $q_1$.
I multpli di $q_1$ che ci interessanno sono solo quelli che vanno da $q_1*2$ a $q_1*p$, gli altri sono maggiori di $n$.
Ora il numero $k=q_1*2$ è sicuramente un multiplo di $q_1$ ma è multiplo anche di $2$ e in quanto tale è già stato CANCELLATO quando hai esaminato il $2$. Chiaro?
Lo stesso ragionamento lo puoi fare (lo devi fare) per tutti gli altri multipli di $q_1$ usando gli interi compresi tra $2$ e $p$ incluso.
Non solo, il medesimo ragionamento lo rifai per tutti gli interi $q_i$ maggiori di $q_1$ e minori $n$.
Da ciò ne concludi che tutti i numeri "cancellabili" sono già stati eliminati quando sei arrivato a $p$.
Ok?

Passo e chiudo

Cordialmente, Alex

[gamer07]

"axpgn":Che fatica ...

I multpli di $q_1$ che ci interessanno sono solo quelli che vanno da $q_1*2$ a $q_1*p$, gli altri sono maggiori di $n$.
Ora il numero $k=q_1*2$ è sicuramente un multiplo di $q_1$ ma è multiplo anche di $2$ e in quanto tale è già stato CANCELLATO quando hai esaminato il $2$.

Finalmenteee !
Hai usato le paroline magiche.
ma dillo prima allora no?!

Credo che se avessi usato altre parole e dato per scontato qualcosa, continuava a mancarmi un anello della catena, almeno nella mia testa.

Convieni con me però che le altre risposte(forse la penultima tua era più vicina) erano un pò distanti ?

Ho un'ultima domanda, un pelino off topic ma sempre in linea con quanto detto fin ora: come ci si è accorti che la radice quadrata per questo scopo avesse questo potere ?! Come ci si arriva?!
Sono curioso di cosa ha potuto osservare la persona se ne è accorta(non credo sia stato Eratostene, perchè questa è un'ottimizzazione del crivello arrivata dopo)
Ciao e davvero grazie per la pazienza

[axpgn]

"gamer07":Convieni con me però che le altre risposte(forse la penultima tua era più vicina) erano un pò distanti ?

No.

Chissà chi ha notato per primo 'sta cosa, ma penso l'abbiano capito presto perché bastano pochi conti per vederla ...
Poi in Matematica occorre sia il ragionamento che l'intuizione (e talvolta anche tanta pazienza )

Cordialmente, Alex