Numeri primi

[Simone Masini]

Ho letto su wikipedia che per vedere se un numero è primo è sufficiente dividerlo per tutti i primi precedenti

e vedere se i resti sono tutti diversi da zero Perchè?

[Gi81]

Che cosa non ti torna in questa asserzione? Dici che non è sufficiente?

[ghira1]

"Simone Masini":Ho letto su wikipedia che per vedere se un numero è primo è sufficiente dividerlo per tutti i primi precedenti

e vedere se i resti sono tutti diversi da zero Perchè?

Basta farlo con i primi fino alla radice quadrata del numero.

[axpgn]

Scusa Simone Masini, puoi dirci la tua definizione di numero primo?

[hydro1]

C'è puzza di troll...

[axpgn]

Non è un troll ma ... ha un suo percorso, diciamo così

[Simone Masini]

si il percorso c'è! Un numero è primo soltanto se è divisibile per se stesso e per l'unità(definizione standard)
Quindi significa che diviso per tutti i numeri precedenti il potenziale numero primo deve dare resto un intero
Adesso tra tutti i numeri precedenti ci sono tutti i pari precedenti che danno per resto un intero quando dividono
un dispari Eliminati questi rimangono tutti i dispari precedenti ma wikipedia dice di prendere tra questi ultimi solo i primi (che dovrei aver trovato precedentemente) Perchè?

[axpgn]

Perché se un dispari non è primo, allora sarà divisibile per (almeno) un altro dispari "più piccolo" di esso.
Ne consegue che è inutile dividere il "potenziale" primo (chiamiamolo $a$) per un numero dispari composto minore di esso (chiamiamolo $d$), dato che questo numero composto (cioè $d$) è sicuramente divisibile per un numero primo minore di esso (chiamiamolo $p$) e quindi il "potenziale" primo (cioè $a$) sarà già stato "testato" per $p$ (cioè hai già provato a dividerlo per $p$ prima di provare a dividerlo per $d$ e se non è divisibile per $p$, sicuramente non è divisibile per $d$)

Cordialmente, Alex

[P_1_6]

potresti anche moltiplicare tutti i numeri primi dispari fino ad $n$ una sola volta e trovare tutti i numeri primi fino ad $n^2$
testando se un dispari maggiore di $n$ ed il prodotto dei numeri primi dispari fino ad $n$ hanno massimo comun divisore uguale ad $1$
Questo è solo per divertirti a pensare
io userei l'algoritmo AkS

[Simone Masini]

nel momento in cui dici che è inutile dividere il "potenziale" primo per un dispari composto come fai a sapere che il divisore dispari è composto e non è primo ? dovresti fare due casi

[Lo_zio_Tom]

"Simone Masini": Un numero è primo soltanto se è divisibile per se stesso e per l'unità(definizione standard)

definizione standard che si trova sul Manuale delle giovani marmotte...perché usando la definizione che hai dato anche 1 sarebbe primo e ciò è evidentemente FALSO

[axpgn]

@Simone Masini

Oh, cavolo!
L'enunciato dice "per tutti i primi precedenti" quindi quando arrivi a testare il "potenziale" primo $a$ sai già quali sono i dispari primi e quali composti!