numeri primi in java

[Bottos]

Scusate il disturbo,
esiste qualche funzione, qualche metodo qualche package o qualsiasi cosa in java, che datogli un numero restituisce se è un numero primo o meno ??

Se esiste mi spieghereste anche il suo funzionamento ??

Grazie mille a tutti
Bottos

[br1]

Ho il sospetto che tu non stia parlando di javascript... ti sposto su Programmazione.

ciao

[Nosferatu]

Se invece intendevi JavaScript, io tempo fa avevo scritto questo:

Number.prototype.isPrime = function() {
   if (this > 2 && this % 2 == 0)
      return false;
   for (var i = 3, l = Math.sqrt(this); i <= l; i += 2)
      if (this % i == 0)
         return false;
   return true;
};

Funge così:
var pippo = 5;
alert(pippo.isPrime()); //true
pippo = 3333;
alert(pippo.isPrime()); //false


Va benone per numeri relativamente piccoli.
In Java basta far diventare il prototipo una funzione.
Se vuoi ulteriori dettagli sul funzionamento chiedi pure.

[Storm Sentry]

in java la cosa è praticamente simile...

public static boolean prim (int a) {
    if (a==1) return false;
    if (a < 3) return true;
    for (int k = 2 ; k <= Math.sqrt(a) ; k++) {
      if (a%k == 0) return false;
    }
    return true;
  }

p.s. : Nosferatu...dai diablerizzami....sono un debole malkavian...

[Nosferatu]

Originariamente inviato da Storm Sentry
in java la cosa è praticamente simile...
[...]
p.s. : Nosferatu...dai diablerizzami....sono un debole malkavian...

:quote:

Se posso vantarmi... la mia versione in JavaScript è ottimizzata, la tua in Java no

Controlla le differenze tra i codici. Non hai fatto gli stress-test, vero?

[Nosferatu]

Ecco il tuo metodo Java ottimizzato.
Ora ad ogni ciclo for la VM non è costretta a ricalcolarsi una radice quadrata che non è cambiata.
Inoltre l'incremento salta tutti i numeri pari, perché il modulo 2 viene eseguito a priori.

public static boolean prim (int a) {
   if (a > 2 && a % 2 == 0)
      return false;
   for (int i = 3, l = Math.sqrt(a); i <= l; i += 2)
      if (a % i == 0)
         return false;
   return true;
};

Niente autografi, prego.

[Bottos]

Grazie mille ragazzi

E se vi dicessi che devo creare una soluzione ricorsiva per il calcolo dei primi n numeri primi sapreste dirmi qualcosa ?

[Storm Sentry]

Ecco il tuo metodo Java ottimizzato.
Ora ad ogni ciclo for la VM non è costretta a ricalcolarsi una radice quadrata che non è cambiata.
Inoltre l'incremento salta tutti i numeri pari, perché il modulo 2 viene eseguito a priori.

public static boolean prim (int a) {
   if (a > 2 && a % 2 == 0)
      return false;
   for (int i = 3, l = Math.sqrt(a); i <= l; i += 2)
      if (a % i == 0)
         return false;
   return true;
};

Niente autografi, prego.

ma quali autografi...POMODORI IN FACCIA !!!

scherzi a parte,il programma cosi' funziona meglio, il doppio assegnamento nel for non l'avevo mai visto, solo ke ci sono DUE PROBLEMINI NEL TUO CODICE!

innanzi tutto cosi' non funziona perchè all'intero l assegni un double quindi devi usare un cast...ma poco importa...

secondariamente il programma SBAGLIA NEI CASI BASE...e cioè dice che sia 0 che 1 sono numeri primi, in quanto lo 0 è per definizione multiplo di tutti i numeri, mentre l'uno non è primo per definizione.
La tua procedura corretta è cosi':

public static boolean bol (int a) {
   if (a < 3) return (a>1);
   for (int i = 3, l = (int) Math.sqrt(a); i <= l; i += 2)
      if (a % i == 0)
         return false;
   return true;
}

ora applaudi me!

[Storm Sentry]

prima che mi guardiate come un pazzo....vi dico perchè 1 non è primo e perchè 0 è multiplo di tutti i numeri.

Definizione di divisore:

"a è un divisore di b" se esiste un numero intero k tale che ka = b; in questo caso si dice anche che "b è multiplo di a"

quindi 2 è un divisore di 6 perchè esiste un intero (3) che moltiplicato a 2 dà 6.

Ora....

5 è un divisore di 0???
esiste un numero intero che moltiplicato epr 5 dia 0?
si...proprio lo 0.
ma quindi anche 3 è divisore di 0...
..4 è divisore di 0...
6 è divisore di 0...

etc etc etc...

quindi 0 è multiplo di tutti i numeri.

Per quanto riguarda l'1 primo o no...vi rammento la definizione rigorosa di numero primo:

"p è un numero primo se e solo se:

1) p>1;
2) p ha come divisori positivi solamente 1 e sè stesso"

da cui segue immediatamente il fatto che 1 non sia primo.

non mi sto inventando tutto...posso provare che quello che sto dicendo sia vero!

[Nosferatu]

Oh mio mentore matematico! Mio Sol!

BTW, mi ero esclusivamente concentrato sul codice, non mi ricordavo esattamente la definizione di primo, lo zero lo avevo ignorato (e anche tu mi pare), e l'uno ero convinto che fosse primo.
Tra l'altro l'ottimizzazione migliore non è l'estrazione della radice, ma il ciclo con incremento doppio.
Ho vatto varie prove statistiche, e non sembra avere senso ottimizzarlo ulteriormente, almeno per numeri piccoli.