[débutant]Trouver des nombres premiers

**Sébastien L** · 17/10/2006, 10h22

Bonjour,

Je suis débutant en programmation et je dois réaliser un petit programme Java, mais je n'obtiens aucun résultat...pourtant, j'y ai passé des heures

Pourriez-vous me remettre sur la voie?

Merci beaucoup,

Sébastien

Voici l'énoncé du problème:

Un nombre premier est un nombre entier positif qui est divisible uniquement par lui-même et par un.

a. Spécifiez la pré- et postcondition une méthode permettant de calculer le nombre de nombres premiers entre l'entier min et l'entier max.

b. Ecrivez le corps de cette méthode sans utiliser de boucle for.

Ma réponse:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 /**
 * Classe renvoyant le nombre de nombres premiers entre les entiers naturels x et y.
 * 
 * @author  Sébastien 
 * @version 16/10/2006
 */
public class Premier
{
 
    //Méthode
 
 
    /** 
     * @param  min et max deux int positifs
     * @return     renvoie le nombre de nombres entiers entre min et max
     */
 
    public int premier()
 
    {
        int i = 5;  //correspond à min
        int y = 27; //correspond à max
 
        double entier = 0.0;
        int comptepremier = 0;
 
        int denum = 0;
        boolean cond = true;
        int reste = 0;
 
 
 
        while(i<y){
 
            denum = i-1;
 
            while( (denum>1) && (  cond = true )) {
 
                reste = i % denum;
 
 
                if ( (i % denum) != 0) {               
 
                   cond = true;
 
 
                   }
                   else{
                       cond = false;
 
                   }
 
                   denum = denum - 1;
 
               }
               //Fin de la boucle while interne
 
               if(cond = true){
 
                   comptepremier++;
 
               }
 
               i+=1;
 
           }//Fin de la boucle while externe
 
           return comptepremier;
 
    }//Fin de la méthode premier
 
}//Fin de la classe Premier

Et la classe test:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 /**
 * Classe testant Premier
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public class Test
{  
 
    public static void main(String args[]){
 
        Premier obj = new Premier();
 
       System.out.println(obj.premier());
    }
}

**thibaut** · 17/10/2006, 10h24

Ton algorythme est il bon pour vérifier tes nombres premiers ?

**McFoggy** · 17/10/2006, 10h47

Salut,

ton algorithme me semble à peu près bon à l'exception de la condition d'arrêt de la boucle principale.
Après si je peux me permettre de te donner quelques conseils:

répond aux questions que l'on te pose, à savoir expose tes pré & posts conditions
utilise des noms de variable explicite (min pr le minimum, ...)

En utilisant des noms de variables un petit peu mieux adaptés ton programme devient nettement plus lisible, compréhensible et debuggable:

Code JAVA :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package test;
 
public class PremierTest {
 
	/**
         * @param args
         */
	public static void main(String[] args) {
		int min  = Integer.parseInt(args[0]);
		int max = Integer.parseInt(args[1]);
 
		int current = min;
		int diviseur = 0;
		boolean isPremier = true;
		int nbPremier = 0;
 
		while (current <= max) {
			isPremier = true;
			diviseur = current - 1;
			while (diviseur > 1 && isPremier) {
				isPremier = (current%diviseur!=0);
				diviseur--;
			}
			if (isPremier) {
				nbPremier++;
				System.out.print(current + " ");
			}
			current++;
		}
 
		System.out.println(" => " + nbPremier + " numbers found between " + min + " & " + max);
	}
}

Matthieu

**iohack** · 17/10/2006, 11h05

while( (denum>1) && ( cond = true )) {

Ca c'est une affection, pour effectuer une comparaison c'est l'opérateur == :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
while( (denum>1) && (  cond == true )) {

**®om** · 17/10/2006, 12h21

Envoyé par iohack

Ca c'est une affection, pour effectuer une comparaison c'est l'opérateur == :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
while( (denum>1) && (  cond == true )) {

Et comme c'est un booléen:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

while ((denum>1) && cond)

**iohack** · 17/10/2006, 12h43

Oui vais vu qu'il débute et que c'est un exercice, je doute que son prof apprécie ce genre de raccourcis ( à mois que ce dernier ne soit adepte d'assembleur ou de programmation obscure en c )

**®om** · 17/10/2006, 14h24

Envoyé par iohack

Oui vais vu qu'il débute et que c'est un exercice, je doute que son prof apprécie ce genre de raccourcis ( à mois que ce dernier ne soit adepte d'assembleur ou de programmation obscure en c )

Pour tous les profs que j'ai eu, aucun n'appréciait le machin == true, ils disaient, dans ce cas on met machin seulement...

**McFoggy** · 17/10/2006, 14h31

Envoyé par ®om

dans ce cas on met machin seulement...

C'est clair que question lisibilité c'est mieux à condition de bien choisir comment on écrit ses expressions booléennes et ses noms de variables.
quand tu vois : if (j==true)
par rapport à : if (isPremier)
Pour moi y a pas photo quant a savoir laquelle des deux écritures je préfère.

Matthieu

**otsgd** · 17/10/2006, 15h26

Salut,

Juste deux conseils pour améliorer les perfs

- Commences à diviser par 2, tu élimineras d'un coup tous les nombres pairs
- Arrêtes-toi de diviser quand diviseur <= racine_current et non diviseur < current , racine_current étant bien la racine carrée de current arrondie au nombre supérieur (c'est juste des maths, si n = pq, soit p <= sqrt(n), soit c'est q).

**Sébastien L** · 18/10/2006, 22h10

Salut!

Merci beaucoup pour votre aide!

Maintenant, ça marche

Si vous voyez encore des trucs à améliorer, je suis preneur...

otsgd, je n'ai pas compris ton 2ème conseil...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
/**
 * Classe renvoyant le nombre de nombres premiers entre les entiers naturels x et y.
 * 
 * @author Leboutte Sébastien 
 * @version 17/10/2006
 */
 
public class Premier
{
 
    //Variables d'instance
 
    int min;
    int max;
 
    //Constructeur
 
    public Premier(int x, int y){
 
         min = x;
         max = y;
    }
 
 
    //Méthode
 
 
    /** 
     * @pre  min et max sont deux entiers naturels positifs
     * @post renvoie le nombre de nombres premiers compris entre min et max
     */
 
    public void premier()
 
    {
 
        //Variables locales
 
 
        int current = min+1;
        int nbPremier = 0;
        int diviseur = 0;
        boolean isPremier = true; 
 
 
 
 
        while(current<max){
 
            isPremier = true;
 
            diviseur = current-1;
 
 
            if(current%2 == 0){
 
                current++;
 
            }
 
            else{
 
            while( diviseur>2 &&  isPremier) {
 
                isPremier = (current % diviseur != 0);
                diviseur--; 
            }
 
                if (isPremier) {               
 
                   nbPremier++;
                   System.out.print(current + " ");
 
                   }
 
                   current++;
 
           }
 
        }
 
               System.out.println(" => " + nbPremier + " nombres premiers entre " + min + " & " + max);
 
     } //fin de la méthode premier
 
 
 
}//Fin de la classe Premier

Et la classe test...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Classe testant Premier
 * 
 * @author Leboutte Sébastien
 * @version 17/10/2006
 */
public class Test
{  
 
    public static void main(String args[]){
 
        Premier obj = new Premier(2,100);
 
       obj.premier();
    }
}

Voici ce que j'ai en sortie...

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 => 24 nombres premiers entre 2 & 100

Encore merci!

Seb

**thibaut** · 19/10/2006, 09h36

Si ça t'intéresse j'ai développé un bout de code pour trouver tout les nombres premiers entre 0 et n, par contre si quelqu'un à un algorythme plus puissant je suis preneur (je sais qu'il en existe, ça me rappelle un bon vieux DS de math):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Premier {
 
    public static void main(String[] args) {
        Premier test = new Premier();
        long duration;
        long start;
        long end;
 
        start = System.currentTimeMillis();
        test.premier(200000);
        end = System.currentTimeMillis();
        duration = end - start;
        System.out.println("Temps écoulé = " + (duration / 1000.00) + " s");
    }
 
    private int[] premiers;
 
    public void premier(int end) {
        premiers = new int[(end / 2) - (end / 10)];
 
        int pos;
        int current;
        int number;
 
        int lastIndex = 0;
 
        boolean premier;
        boolean go;
 
        for (current = 1; current < end; current++) {
 
            switch (current) {
                case 1:
                case 2:
                case 3:
                case 5:
                    premier = true;
                    go = false;
                    break;
               default:
                   premier = true;
                   go = true;
 
            if ((current - 5) % 10 == 0) {
                premier = false;
                go = false;
            }
 
            if (current % 2 == 0) {
                premier = false;
                go = false;
            }
 
        for (pos = 4; (pos < lastIndex) && go; pos++) {
            number = premiers[pos];
 
            if (current % number == 0) {
            premier = false;
            go = false;
            }
        }
        }
 
        if (premier) {
          premiers[lastIndex] = current;
          lastIndex++;
        }
    }
    }
}

**otsgd** · 19/10/2006, 10h38

Sébastien,
Pour le 2ieme conseil, tu veux savoir si 12769 est premier, s'il ne l'est pas, alors on peut l'écrire sous la forme 12769 = p * q. La racine de 12769 est 113, donc 113 * 113 = 12769. Maintenant, il existe peut-être d'autres p' * q' qui donnent 12769, mais ce qui est sûr c'est que soit p' < 113, soit q' < 113. C'est plus clair comme ça ? Par sécurité, je m'arrêtes toujours à la racine + 1.

Par contre, tu continues de partir de la fin (diviseur = current -1), ca ralenti le traitement. Si tu pars du début (de 2 en fait), tu n'auras pas à faire de cas particulier et ça ira plus vite.

thibaut, effectivement il y a beaucoup plus rapide :
- Il faut commencer à diviser par 2 et s'arrêter à la racine du nombre à tester.
- On peut meme se contenter de diviser par les nombres premiers qui précèdent la racine du nombre à tester.

Voilà un code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
public class PrimesComputer2 {
 
	private int[] primes;
	private int countPrimes;
 
	public int[] computePrimes(int end) {
		primes = new int[end / 10]; // Only for end > 100000
		int sqrt;
		boolean isPrime;
 
		for (int idx = 2; idx <= end; idx++) {
			isPrime = true;
			sqrt = (int) Math.sqrt(idx);
 
			for (int jdx = 0; primes[jdx] != 0 && primes[jdx] <= sqrt && isPrime; jdx++) {
				if ((idx % primes[jdx]) == 0)
					isPrime = false;
			}
 
			if (isPrime)
				primes[countPrimes++] = idx;
		}
 
		return primes;
	}
 
	public int[] getPrimes() {
		return primes;
	}
 
	public int getCountPrimes() {
		return countPrimes;
	}
 
	public static void main(String[] args) {		
		PrimesComputer2 pc = new PrimesComputer2();
 
		long start = System.currentTimeMillis();
		pc.computePrimes(1000000);
		System.out.println("Computing " + pc.getCountPrimes() + " primes in " 
				           + (System.currentTimeMillis() - start) + " ms");		
	}
}

**McFoggy** · 19/10/2006, 10h47

Envoyé par otsgd

thibaut, effectivement il y a beaucoup plus rapide :
- On peut meme se contenter de diviser par les nombres premiers qui précèdent la racine du nombre à tester.

C'est ce que thibaut fait à quelques erreurs d'index prêt sur sa boucle de division par les nombres
premiers trouvés.

Sinon le plus rapide à mon avis, tout en restant très simple à implémenter, est le crible d'Erathostène.

A vos claviers...

**otsgd** · 19/10/2006, 10h59

Envoyé par McFoggy

C'est ce que thibaut fait à quelques erreurs d'index prêt sur sa boucle de division par les nombres premiers trouvés.

Autant pour moi, je n'avais pas assez regardé.

Sinon le plus rapide à mon avis, tout en restant très simple à implémenter, est le crible d'Erathostène.

A vos claviers...

Pour ceux que ça intéresse :
On désigne sous le nom de crible d'Eratosthène une méthode de recherche des nombres premiers plus petits qu'un entier naturel n donné.
Pour ceci, on écrit la liste de tous les nombres jusqu'à n.
.On élimine 1.
.On souligne 2 et on élimine tous les multiples de 2.
.Puis on fait de même avec 3.
.On choisit alors le plus petit nombre non souligné et non éliminé ici 5,
et on élimine tous ses multiples.
.On réitère le procédé jusqu'à la partie entière de la racine de n.
Les nombres non éliminés sont les nombres premiers jusqu'à n.

**otsgd** · 19/10/2006, 11h42

Je dois coder avec mes pieds parceque j'obtiens de mauvais résultats (255 secondes pour le crible d'eratosthene en allant jusque 1.000.000 et moins d'une seconde avec le code donné au-dessus).

Ca doit bien ressembler à ça non ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
public class PrimesComputer3 {
 
	private int[] primes;
	private int countPrimes;
 
	public void computePrimes(int end) {
		primes = new int[end - 2];
		int current;
		int currentIndex;
		boolean isEnded = false;
 
		for (int idx = 0; idx < primes.length; idx++)
			primes[idx] = idx + 2;
 
		current = primes[0];
		currentIndex = 0;
		while (!isEnded) {
			for (int idx = currentIndex + 1; idx < primes.length; idx++)
				if (primes[idx] != -1 && (primes[idx] % current) == 0)
					primes[idx] = -1;
 
			isEnded = true;
			for (++currentIndex; currentIndex < primes.length && isEnded; currentIndex++)
				if (primes[currentIndex] != -1) {
					current = primes[currentIndex];
					isEnded = false;
				}
		}
 
		for (int idx = 0; idx < primes.length; idx++)
			if (primes[idx] != -1)
				countPrimes++;
	}
 
	public int[] getPrimes() {
		return primes;
	}
 
	public int getCountPrimes() {
		return countPrimes;
	}
 
	public static void main(String[] args) {		
		PrimesComputer3 pc = new PrimesComputer3();
 
		long start = System.currentTimeMillis();
		pc.computePrimes(1000000);
		System.out.println("Computing " + pc.getCountPrimes() + " primes in " 
				           + (System.currentTimeMillis() - start) + " ms");		
	}
}

**otsgd** · 19/10/2006, 12h10

Correction, j'avais oublié la racine carré.

Avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
int sqrt = (int) Math.sqrt(end);

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
isEnded = true;
for (++currentIndex; current < sqrt && currentIndex < primes.length && isEnded; currentIndex++)
   if (primes[currentIndex] != -1) {
	current = primes[currentIndex];
	isEnded = false;
   }

j'obtiens cette fois ci 1.329s contre 0.469s pour la méthode précédente.

Pour l'instant, c'est donc moins rapide, quelqu'un voit-il pourquoi ?

**McFoggy** · 19/10/2006, 12h12

Pr le calcul des nb premiers < à 1000000

Erathostene : 32ms
Ton algo précédent : 359 ms

Voilà mon implémentation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package test;
 
import java.util.Arrays;
 
public class Erathostene {
	public int nbPremiers(int max) {
		int sqrtMax = (int) Math.sqrt(max) + 1;
		boolean[] premiers = new boolean[max];
 
		Arrays.fill(premiers, true);
 
		for (int idx = 1; idx <= sqrtMax; idx++) {
			if (premiers[idx]) {
				fill(premiers, idx+1, max);
			}
		}
 
		int nbPremiers = 0;
		// On demarre a idx = 1 ie val = 2 car 1 n'est pas considéré comme premier
		for (int i = 1; i < premiers.length; i++) {
			if (premiers[i]) {
				nbPremiers++;
//				System.out.print(i + " ");
			}
		}
		return nbPremiers;
	}
 
	private void fill(boolean[] premiers, int nbPremier, int max) {
		for (int current = nbPremier*2 - 1; current < max; ) {
			premiers[current] = false;
			current = current + nbPremier;
		}
	}
 
	/**
         * @param args
         */
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int nb = new Erathostene().nbPremiers(1000000);
		long end = System.currentTimeMillis();
		System.out.println(nb + " nb premiers found in " + (end - start) + " ms");
	}
}

**otsgd** · 19/10/2006, 12h21

Ca va etre dur de faire mieux.
Très beau code en tout cas, c'est bien vu.

[débutant]Trouver des nombres premiers

Langage Java

Discussions similaires

Partager

Partager