// Remplir la table 'table' des n premiers nombres premiers (ici n=100 millions)

package nombrespremiers;
public class NombresPremiers {
    public static void main(String[] args) {
        int n = 100000000;  //Dimension de la table 'table' (à saisir chaque fois)
        int[] table; // Table de nb premiers avec n places [0..n-1]
        table = new int[n];
        table[0] = 1; table [1] = 2; table[2] = 3; //nb premiers donnés
        int candidat = 3; //premier entier impair candidat à être premier
        int position; //position dans table pour recherche divisibilité
        boolean premier, trouve;
        int reste; //reste dans division (variable de travail)
        int limite; //plus grand entier diviseur possible: racine de candidat
//Boucle de remplissage des places de 3 à n-1
        for(int place=3; place<n; place++){           
   //Boucle recherche du nb premier suivant (candidat)
            premier = false;
            while(premier == false){
                candidat = candidat+2;            
       //Boucle recherche divisibilité de candidat des positions 2 à limite 
                position = 2;
                limite = (int) Math.sqrt((double)candidat);
                trouve = false;
                while(trouve==false && table[position]<=limite) {
                    reste = candidat % table[position];  
                    if (reste == 0) trouve=true; else position++;
                } 
                if (trouve==false) premier = true;//candidat est premier                                    
            }
            table[place] = candidat; //-> dans la table                    
        }
        System.out.println(candidat); //impression du dernier nb de la table
        System.exit(0); 
    }    
}
// Cent millionième nb premier : 2.038.074.739, trouvé en 1535 secondes
// Remarque : puisque  2**31 = 2.147.483.648 on ne pouvait guère aller plus loin
// Le 99.999.999ème nb premier est  2.038.074.713...