[Java] Funzione restituisce risultato teoricamente scorretto

[Patrick Jane]

Ciao a tutti,

Scusate il titolo, ma non sapevo proprio come definire il problema.

Ho una (semplicissima) funzione che mi permette di individuare se un numero è primo.

Sapete spiegarmi per quale ragione, in questo modo funziona:

  public static boolean isPrimo(int n) {
    if(n==1) return false;
    else if((n%2==0) && (n!=2)) return false;
	
    for(int i=3; i<n; i+=2) {
      if((n%i == 0) && (n!=i)) return false;
    }
    
    return true;
  }

Ma se faccio

  public static boolean isPrimo(int n) {
    if(n==1) return false;
	else if((n%2==0) && (n!=2)) return false;
	
	for(int i=3; i<((int)Math.sqrt(n)); i+=2) {
	  if((n%i == 0) && (n!=i)) return false;
	}
    
	return true;
  }

Aggiungendo cioè (int)Math.sqrt(n) questa non funziona più, dicendomi che anche 9 (e gli altri dispari) sono primi?

Grazie! ^^

[andbin]

Originariamente inviato da Patrick Jane
Aggiungendo cioè (int)Math.sqrt(n) questa non funziona più, dicendomi che anche 9 (e gli altri dispari) sono primi?

E perché dovresti usare sqrt? Basta che vai fino a metà di N (es. se N è 13, basta che provi al massimo diviso 6).

[desa]

L'istruzione

&& (n!=i)

è inutile, visto che in entrambi i casi la condizione di uscita dal for lo impedisce.

Nel secondo caso è proprio la condizione di uscita a essere sbagliata: devi usare il minore o uguale, non il minore stretto.

[Patrick Jane]

Originariamente inviato da andbin
E perché dovresti usare sqrt? Basta che vai fino a metà di N (es. se N è 13, basta che provi al massimo diviso 6).

Perchè risparmierei molte iterazioni.. ad esempio:

1000/2 = 500
sqrt(1000) = 31.

Arrivato a 31 so che numeri maggiori di esso non possono essere un multiplo.

@desa: ok. Ma sul secondo caso ti riferisci al fatto che non ho messo <= ?

[desa]

La condizione di radice quadrata è più "stringente". Se arrivato alla radice quadrata non hai ancora trovato un divisore, non ne troverai andando oltre... a parte il numero stesso, naturalmente.

[desa]

Sì, esatto: fallisce per tutti i quadrati perfetti.

[Patrick Jane]

Ok, modificato! Grazie per il suggerimento!

Non ho capito il motivo.. comunque ora funziona :grat: (cioè, non stampa più i dispari).

Grazie!!