Trovare numeri primi

[mathys]

Ciao ragazzi ho trovato questo codice per verificare se un numero e' primo:

int IsPrimo(int x)
{
int i = 0;
for(i = 2; i <= x / 2; i++)
{
if (x % i == 0) return 0;
}
return 1;
}


il codice funziona ovviamente ma non riesco a capire quel (x/2), dove l'ho preso non lo spiega, potete aiutarmi a capire?
se provo ad usare x invece di x/2 il codice non funziona bene ovviamente.

[Faussone]

Un numero diviso per un altro può dare un numero intero maggiore di 1 fintanto che il divisore non è maggiore della metà del dividendo, se no già si sa che il quoziente non può essere intero maggiore di uno (essendo minore di 2...)

[mathys]

non ho capito cos avuoi dire, potresti spiegarmelo in parole piu semplici?
scusa

[mathys]

int IsPrimo(int x)
{
int i = 0;
for(i = 2; i <= x / 2; i++)
{
if (x % i == 0) return 0;
}
return 1;
}

cioe se chiamo la funzione con x = 5, avrei che il ciclo for andrebbe con i da 2 a 2, giusto?
cioe' non capisco sto passaggio

[Faussone]

"mathys":non ho capito cos avuoi dire, potresti spiegarmelo in parole piu semplici?
scusa

E' un concetto da scuola elementare

Prendo 13, provo a dividerlo per 2,3,4,5,6 (in realtà basterebbe dividerlo per tutti i primi minori di 7) e a verificare se ottengo un numero intero, inutile provare a dividerlo per 7 e per numeri più grandi perché comunque già so che otterrei un numero minore di 2: se devo verificare che il numero è primo devo vedere se dividendolo per un altro numero viene un intero maggiore di 1 (ovvio che il numero è divisibile per se stesso).

[Super Squirrel]

il codice credo possa essere migliorato ragionando nel seguente modo:

il metodo è sempre quello di capire se il numero è primo dividendolo per vari divisori e accertandoci che il resto sia diverso da zero, ma possiamo ridurre il numero di divisioni da effettuare.
chiamiamo n il nostro numero e ricordiamo che un numero primo è divisibile solo per 1 e se stesso.
scriviamo n come prodotto di due numeri naturali: n=a*b con a<=b
si possono avere due casi:
- n è primo allora a=1 e b=n;
- n non è primo allora a e b possono assumere valori che vanno da 2 a n/2(come mostra il codice da te postato).
essendo a<=b se a*a>n sarà anche a*b>n.
partendo quindi da a=2, se a^2>n allora n è primo, se a^2<=n allora a è un probabile divisore.

per esempio controlliamo se 71 è primo (con il codice da te postato avremmo dovuto dividerlo per 2,3,4,5,...,34,35).
2^2=4<71
3^2=9<71
4^2=16<71
5^2=25<71
6^2=36<71
7^2=49<71
8^2=64<71
9^2=81>71
in questo caso lo dividiamo solo per 2,3,4,5,6,7,8

[Faussone]

"Super Squirrel":il codice credo possa essere migliorato ragionando nel seguente modo:

[....]
in questo caso lo dividiamo solo per 2,3,4,5,6,7,8

Verissimo.
In realtà è anche inutile provare a dividerlo per numeri pari maggiori di 2 per vedere se è primo (se fosse divisibile per un numero pari maggiore di 2 allora sarebbe comunque divisibile per 2), è inutile pure in generale provarlo a dividere per numeri non primi, ma questo è meno usabile nell'immediato.

In ogni caso quando i numeri iniziano a essere grandini i calcoli da fare sono comunque tantissimi, non esiste un metodo veloce per verificare se un numero è primo o per trovare i fattori primi di un numero, tanto è vero che gli algoritmi di crittografia si basano sulla difficoltà ( o meglio sul costo) della fattorizzazione...

[vict85]

A meno di usare il crivello su \(\lceil \sqrt{N}\rceil\) non direi che tu possa in generale usare i numeri primi per il test, seppur ci siano dei modi per sfruttare i numeri primi piccoli per ridurre l'insieme. Per capirci, se tu elimini 2 e 3 allora devi considerare solo numeri che abbiano resto 1 e 5 con 6 ovvero, partendo da 5 devi sommare due e poi sommare 4, poi di nuovo 2 e così via. Più primi consideri più riduci il tutto, seppur il vantaggio sia decrescente.