Newsgroup: it.comp.java
Titolo: Fino a che numero posso calcolare

Volevo farmi una tab.  di numeri primi in java.
Con questo sorgente fino a che numero posso arrivare?
//inizio
public class Numeri{
 static long a,i;
 public static void main (String[] args){
  for(a=1;a>0;a++){
   for(i=2; i<=a; i++) {
    if (i==a) {
      System.out.print(a+"   ");//"\nGrande! Un numero primo!");
        break;
     }
       if (a%i==0) {
        //System.out.println()
        break;
       }
    }
  }
  }
 }
 //fINE

JPluto wrote:

Ciao... il valore massimo di a e i č 9223372036854775807, bastava 
andarlo a cercare nelle specifiche del linguaggio 
http://java.sun.com/docs/books/jls/second_edition/html/j.title.doc.html
Ovvio che non so dirti quale sia il numero primo piů alto a cui puoi 
arrivare... :)
Cmq al di la di questo... non vorrei sbagliarmi ma non sono sicuro che 
l'operatore % funzioni con i long. Difatti sono a virgola mobile e 
quindi le divisioni non danno mai resto... Per quanto ne so io % 
funziona solo con int (come in tutti i linguaggi di programmazione, 
credo). Inoltre penso che questo codice potrebbe essere ampiamente 
ottimizzato...
Gli int cmq arrivano fino a 
2147483647
.
Prova a pensarci un pň...
Ciao
Ivan


credo fino a 2^64-1 :-) I long in java sono 64 bit? Ma è difficile che il
tuo computer possa arrivare fino a quel numero.
Invece di provare fino a dividere fino ad a puoi fermati alla radice
quadrata di a arrotondata per eccesso
ciao

 credo).
Non so se tutti ma molti linguaggi di programmazione hanno int e long 
(entrambi che rappresentano numeri interi) e in tutti l'operatore % 
funziona con entrambi.
Andrea


Come qualcuno ti ha già detto il limite di rappresentazione per i long è 
  9223372036854775807 (2^63-1), metre per gli int è 
2147483647
 (2^31-1).
In realtà temo che dovrà fermarsi molto prima di quest'ultima cifra.
Per verficare che un numero N non è primo il programma calcola il resto 
di N-2 divisioni.
Dato che i numeri primi sono abbastanza pochi rispetto agli altri 
possiamo dire che per verificare quali sono i numeri primi nei primi N 
numeri dovremo calcolare un pò meno di:
1 + 2 + ... + N-2 resti
cioè:
((N-2)^2)/2
Per N = 2^31-1 si ha ~2*10^18
2 miliardi di miliardi di operazioni!!!
Anche suppoendo di fare un miliardo di operazioni al secondo (e ti 
garantisco che il tuo PC ne farà molte meno) si dovrà aspettare la 
bellezza di 73 anni!
A occhio e croce direi che in una giornata di calcolo, co un PC di media 
potenza, dovresti arrivare almeno a 1.000.000 (ma non a 10.000.000).
Ovviamente l'algoritmo può essere ottimizzato. Qualcuno suggeriva di 
fermarsi alla radice quadrata di N arrotondata per eccesso (dato che se 
N = A*B deve essere A<= sqrt(N) o B<=sqrt(N) ).
Ancora potresti dividere solo per i numeri dispari (più il 2, 
ovviamente):se un numero non è divisibile per 2 non lo è per nessun 
multiplo di 2.
In questo modo il numero di operazioni dovrebbe passare (se non ho 
sbagliato i conti) da:
~(N^2)/2
a
~(N^1,5)/4
Una bella differenza direi! Questo dovrebbe permetterti di arrivare al 
miliardo.
Potresti anche prendere in considerazione la possibilità di memorizzare 
  i numeri primi e dividere solo per quelli, ma qui' la cosa (il calcolo 
della complessità) si fa complicata e entra in gioco anche l'occupazione 
di memoria, ti consiglio di cercare su internet qualche documento a 
rigurado.
Cambiando completamente algoritmo sono riuscito a calcolare tutti i 
numeri primi tra 1 e 100 milioni in 15 secondi (tra l'altro con un PC 
non potentissimo). Ora devo scappare e non ho il tempo di descriverlo a 
fondo. L'idea (ovviamente non mia ;-) ) è di prendere una tabella con 
tutti i numeri e segnare quelli che sono multipli di qualche altro. Un 
vantaggio è che non si devono fare divisioni ma solo moltiplicazioni. 
Purtroppo serve una grossa tabella.
Naturalmente un conto è cercare tutti i numeri primi minori o uguali a 
N, altro è cercare di trovare un numero primo di una certa dimensione. 
Ci sono algoritmi che permettono di generare "probabili primi" di 
notevoli dimensioni e altri che permettono di verificare tali categorie 
di candidati.
Andrea

Andrea Polci wrote:

Uh... grazie, evidentemente mi ero confuso :D
Ciao