Bonjour à tous, j'ai fait un algorithme qui calcule les nombres premiers de 0 jusqu'à une limite entrée par l'utilisateur (Crible d'Eratosthène), il m'a l'air correcte quand je le fais pas à pas dans ma tête, mais voilà, il ne marche pas. Voici le code:

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class NbPremier0 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//Déclaration de variables
		Scanner scan=new Scanner(System.in);
		int limite;
		int j=0; //CHANGEMENT
		int i=3;
		int compteur=0;
		List NbPremier=new LinkedList();
		NbPremier.add(2); //CHANGEMENT
				
		System.out.println("Entrez la limite supérieure pour le calcul");
		limite=scan.nextInt();
				
		long debut=System.currentTimeMillis();
		
		 //Boucle principale	
		while(i<=limite){
			
			//Boucle secondaire
			do{
				for(j=0;j<NbPremier.size();j++){
			
					if(i%(int)NbPremier.get(j)==0){ //CHANGEMENT
						compteur++; // Si i et j sont multiples on incrémente compteur
					}
			
					if(compteur>0){ //Si compteur est supérieur à 0
						j=NbPremier.size()+1; //...on met j à la valeur i pour sortir de la boucle CHANGEMENT
					} 
				}
			}
			while((int)NbPremier.get(j)<=Math.sqrt(i)); //CHANGEMENT
				
				if(compteur==0){ //Si compteur==0 après vérification, donc que le nombre i est premier
					NbPremier.add(i);
				} 
				j=0; // On remet j à sa valeur de départ CHANGEMENT
				compteur=0; // On remet compteur à sa valeur de départ
			
				i=i+2; //On incrémente i de 2 à chaque fois pour ne faire les calculs qu'avec les
						// nombres impairs
			
		}
		long fin=System.currentTimeMillis();
		System.out.println(NbPremier);
		System.out.println("Le temps de traitement est de "+(fin-debut)+" ms");
	}
}

Quand je le lance, voilà ce qu'il m'affiche:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
    at java.util.LinkedList.checkElementIndex(Unknown Source)
    at java.util.LinkedList.get(Unknown Source)
    at NbPremier0.main(NbPremier0.java:39)
Je sais bien que cela signifie que je fais une opération avec un élément n'existant pas mais je ne vois pas où, comment ni quand. ..Pouvez-vous m'aider s'il vous plaît? Je vous serais très reconnaissant. Merci d'avance

Bonjour,

sauf erreur le problème vient de l'instruction

(int)NbPremier.get(j)

Pourquoi

for (initialisation ; test ; itération) {
opération;
}

Dans une boucle for, tu vas déjà éxécuter itération puis le test. Quand tu sors de ta boucle:

NbPremier.size() == j

D'où l'erreur.

Je ne comprend pas trop ce que tu veux dire à part que l'erreur vient du

(int)NbPremier.get(j)

peux-tu me réexpliquer s'il te plaît?

Quand tu vas arriver ligne 39 la variable i est égale à la taille de la Collection NbPremier / NbPremier + 2 (après relecture du code).

Quand tu fais un get(X) sur une Collection ou Tableau X doit avoir une valeur comprise en 0 et Collection.size()-1.

Afin de résoudre ton problème, tu peux remplacer par:

NbPremier.get(NbPremier.size()-1)

Yo,

je ne sai pas si les autres réponses t'aide mais en Java il faut faire attention avec les tableau car

si nous avons un tableau de taille 3 (tab[].length ou collection.size() )

tab[0] donne élément 1

tab[1] donne éléments 2

tab[2] donne éléments 3

tab[3] => erreur car tu dépasse la taille du tab

Merci ça marche mieux maintenant j'ai compris d'où venait le problème c'est bien ce que vous disiez. J'ai donc changé

(int)NbPremier.get(j)

par

(int)NbPremier.get(j-1)

Encore merci.

@Schildkrote

As-tu lu ma réponse dans ton autre fil de discussion ?

Oui je l'ai bien vu et merci mais je ne sais pas comment fonctionne et une ArrayList ou une boucle for each. Mais j'ai bien pris en compte ton troisième point. Au final j'ai fait ça:

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class NbPremier0 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//Déclaration de variables
		Scanner scan=new Scanner(System.in);
		int limite;
		int i=2;
		int j=1;
		int k=0;
		int compteur=0;
		List<Integer> NbPremier=new LinkedList();
				
		System.out.println("Entrez la limite supérieure pour le calcul");
		limite=scan.nextInt();
				
		long debut=System.currentTimeMillis();
		
		 //Boucle principale	
		while(i<=limite){
			// Pour lancer la boucle secondaire
			if(NbPremier.size()<2){
				NbPremier.add(i);
			}
			else{
				// Boucle secondaire
				while((int)NbPremier.get(j-1)*(int)NbPremier.get(j-1)<=i){
					// Boucle tertiaire
					while(j<NbPremier.size()){
						if(i%(int)NbPremier.get(j)==0){ 
							compteur++;
						}
						if(compteur>0){
							j=NbPremier.size();
						}
						else{j++;}
					}
				}
				// Si i n'a pas de diviseurs autres que lui-même et 1, il est premier, on l'ajoute à la liste
				if(compteur==0){
					NbPremier.add(i);
				}
			}
			// Remise à zéro des variables pour relancer la boucle principale
			j=1;
			compteur=0;
			if(i>=3){i=i+2;}
			else{i++;}	
		}
		// Sorties
		long fin=System.currentTimeMillis();
		for(k=0;k<NbPremier.size();k++){
			System.out.println(NbPremier.get(k));
		}
		System.out.println("Le temps de traitement est de "+(fin-debut)+" ms");
	}
}

Par contre après quelques essais, j'ai constaté que c'est extrêmement lent, c'est normal? Une ArrayList ou une bouble for each résoudrait ça?

    public static void main(String[] args) {
        int toFind = 100;
        List<Integer> nbPremiers = new LinkedList<Integer>();
 
        nbPremiers.add(2);
        int i = 3 ;
        while( nbPremiers.size() < toFind ) {
            boolean premier = true ;
            for(Integer index=1;index<nbPremiers.size();index++) {
                                if( i%nbPremiers.get(index) == 0 ) {
                    premier = false;
                    break;
                } else if ( nbPremiers.get(index)>Math.sqrt(i) ) {
                    break;
                }
            }
            if( premier ) {
                nbPremiers.add(i);
            }
            i = i+2;
        }
        System.out.println("nbPremiers = " + nbPremiers);
    }

Ci-dessus un exemple d'algorithme. S tu veu de l'aide. MP et je t'aide a comprendre. Je viens de vérifier des nombres sur http://fr.numberempire.com/1130501 et je ne pense pas avoir d'erreur si tu veux le reprendre et que l'on en parle ensemble

-
Edité par pierro75016 20 novembre 2014 à 23:25:46

Oui, ça irait sûrement mieux avec une ArrayList. Remplace juste LinkedList par ArrayList, il n'y a rien d'autre à faire. Oublie la boucle for-each pour l'instant.

La différence, c'est que l'ArrayList est à accès direct car elle utilise un tableau (array). L'accès aux données est en temps fixe. nbPremiers.get(i) prend le même temps pour chaque i.

La linkedListe est une list chainée (linked). Pour atteindre l'élément i, tu dois parcourir toute la liste jusqu'à i. nbPremiers.get(99) prend donc 100 fois plus de temps que nbPremiers.get(0).

Sinon, écris plutôt nbPremiers. En Java, la convention est de commencer les noms de variables (et de fonctions) par une minuscule.

Et puisque tu as spécifié le type d'éléments de la liste, tu peux enlever les (int).

Par contre, je pense toujours que ce n'est toujours pas le crible d'Eratostène (à moins que j'aie mal compris ton premier message et que tu doives juste trouver les nombres premiers, peu importe la méthode).

-
Edité par brubru777 21 novembre 2014 à 1:05:52

Ah oui c'est beaucoup plus rapide, merci. Je pense que le programme est assez bien optimisé maintenant:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class NbPremier0 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//Déclaration de variables
		Scanner scan=new Scanner(System.in);
		int limite;
		int i=2;
		int j=1;
		int compteur=0;
		List<Integer> nbPremier=new ArrayList<Integer>(); // On utilise une ArrayList car plus rapide qu'une LinkedList
		
		// Entrées
		System.out.println("Entrez la limite supérieure pour le calcul");
		limite=scan.nextInt();
				
		long debut=System.currentTimeMillis();
		
		 //Boucle principale	
		while(i<=limite){ // On répète les opérations tant que i est inférieur ou égal à la limite
			// Pour lancer la boucle secondaire, sinon la condition n'est jamais vérifié et cela crée une boucle infinie.
			// On cherche à avoir 2 et 3 dans la liste
			if(nbPremier.size()<2){
				nbPremier.add(i);
			}
			else{
				// Boucle secondaire
				while(nbPremier.get(j-1)*nbPremier.get(j-1)<i){ // Tant que i est supérieur à la racine de l'élément de la liste
					// Boucle tertiaire
					while(j<nbPremier.size()){ // Tant que j est inférieur à la taille de la liste
						if(i%nbPremier.get(j)==0){ // On divise i par les nombres premiers inférieurs à lui (présents dans la liste)
													// Si le reste vaut 0, i a un autre diviseur que 1 et lui-même, il n'est donc pas premier
							compteur++; // Dans ce cas on incrément compteur
							j=nbPremier.size();	// On affecte à j une valeur qui nous fait sortir de la boucle tertiaire
						}
						else{j++;} // Sinon on incrémente j
					}
				}
				// Si i n'a pas de diviseurs autres que 1 et lui-même, il est premier, on l'ajoute à la liste
				if(compteur==0){
					nbPremier.add(i);
				}
			}
			// Remise à zéro des variables pour relancer la boucle principale
			j=1;
			compteur=0;
			if(i>=3){i=i+2;} // Si i est supérieur ou égal à 3, on l'incrémente de 2 à chaque pour ne faire des tests
							//qu'avec des nombres impairs, les pairs étant divisibles par 2 et donc non premiers
			else{i++;} // Sinon on incrémente i	
		}
		// Sorties
		long fin=System.currentTimeMillis();
		for(int k=0;k<nbPremier.size();k++){
			System.out.println(nbPremier.get(k));
		}
		System.out.println("Le temps de traitement est de "+(fin-debut)+" ms");
	}
}

Je ne sais pas si c'est tout à fait le crible d'Eratosthène mais c'est ce que mon prof' m'a demandé donc qu'importe le nom au final. Mais encore merci à tous pour votre aide.

J'ai une dernière question en fait: à partir de 47000, le programme ne se termine ou est beaucoup trop long (5 minutes), du coup je l'arrête avant. Savez-vous pourquoi?

Plus exactement ça marche jusqu'à 46350 mais à partir de 46351, il n'y a plus de fin. Une idée de la raison?

Il y a pas mal de choses que tu pourrais faire pour rendre ton code plus simple, plus clair et plus efficace. Mais globalement, ton algorithme fais un nombre d'opérations proportionnel à limite^2 (ou éventuellement limite * racine carrée de limite). Donc, ça augmente vite.

Une suggestion pour rendre ton code plus lisible. Tu peux créer une fonction

List<Integer> calculerNombresPremiers(int limite)

Ca séparera ton calcul de l'interface. Ca fait plus propre et plus lisible.

EDIT: Avec le crible d'Eratosthène (qui n'utilise pas % mais juste des additions), j'ai les nombres premiers jusqu'à 1 million en 49ms. Tu devrais essayer cet algorithme.

REEDIT: Pour 100 millions, ça prend quand même 1 minute !

-
Edité par brubru777 21 novembre 2014 à 15:07:28