Numeri primi

[Marix]

Ciao a tutti,
come faccio a dimostrare che un numero non è primo? Per esempio il numero 123456789.
Devo anche determinare tutti i numeri primi tra 100 e 120. Come si fa?

[Alexp]

Ciao,
il numero 123456789 non è primo perchè è divisibile per 3.....

Per quanto ne so io, non esistono metodi per ricavare numeri primi, altrimenti tutte le congetture sui primi sarebbero già state risolte......purtroppo bisogna calcolarli tutti "a mano", ossia provare che non sono divisibili per nessun numero se non per se stessi!

[adaBTTLS]

il metodo più classico è il "crivello di Eratostene".
si parte da tutti i numeri e si escludono tutti i multipli di 2,3,5,7,11,....
puoi cercare eventualmente informazioni sul web.
spero ti sia utile. ciao.

[maurer]

Un altro criterio è controllare che $n$ non sia divisibile per nessun numero primo al di sotto della sua radice quadrata...

[silvano38]

Be un modo ci sarebbe ed è quello di far uso del Teorema di Wilson:
Un numero $p$ è primo solo e solo se vale la congruenza:
$(p-1)!+1-=0 (mod p)$
Nel caso tuo devi vedre se il numero $123456788!+1$ è divisibile per $123456789$ ...
Se ci riesci sei a cavallo !!!

[adaBTTLS]

io naturalmente, parlando del crivello di Eratostene, mi riferivo all'altro quesito (numeri primi tra 100 e 200).
per il controllo su un singolo numero ci si può "fermare" ai primi minori della radice quadrata, come suggerito da maurer, ma per quanto riguarda il numero postato già alexp ha risposto che si vede banalmente che non è primo...

[maurer]

Sì, combinando il crivello di Eratostene con quello che ho postato io, trovare i numeri primi tra 100 e 200 diventa abbastanza rapido, direi; visto che il più grande numero primo minore di $sqrt(200)$ è 13, si può concludere che è sufficiente scrivere il crivello per i numeri primi compresi tra 2 e 13.

[silvano38]

Il mio intervento serviva a ricordare scherzosamente il Teorema di Wilson ,visto che in pratica
questi è inapplicabile per numeri di un cert'ordine di grandezza...