Emplacement mémoire tableau [Nombres premiers]

**F.Margaine** · 19/03/2008, 11h23

Bonjour,

Commençant en C, j'ai voulu m'exercer en créant un petit programme qui est censé faire les choses suivantes :

Demander un nombre spécifique.
Faire la liste des nombres de 3 à ce nombre et vérifier s'ils sont premiers.
Enregistrer tous les nombres premiers dans un tableau.
Afficher les nombres premiers trouvés.

Maintenant, voici le code que j'ai créé, dans l'espoir que cela marche :

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
 
#include <stdio.h>
#include <stdlib.h>
 
main()
{
      /* Je déclare toutes les variables. Le tableau a 1000 emplacements pour être "large". */
      int nombre, i, b=1, a=0, premier[1000], chiffre;
      /* Saisie du nombre... */
      printf("Saisir un nombre : ");
      scanf("%d",&chiffre);
      fflush(stdin);
      /* Je crée une boucle de 3 jusqu'au nombre rentré (non inclu) pour les tester */
      for (nombre=3;nombre<chiffre;nombre++)
      {
          /* Une autre boucle afin de tester si le nombre est premier. 
           * Je prends tous les chiffres de 2 à "nombre à tester" et 
           * je regarde leur reste de division. S'il y en a un qui a 
           * pour reste 0, la variable b (comme booléen) passe à 0. 
           * Sinon, elle reste à 1. 
           */
          for (i=2;i<(nombre-1);i++)
          {
              if ((nombre%i)==0)
              {
                 b=0;
              }
          }
          /* Si le nombre est premier, je le rentre dans le tableau. 
           * J'incrémente ensuite le "numéro de case" du tableau 
           * pour le prochain nombre premier. 
           */
          if (b==0)
          {
             premier[a]=nombre;
             a++;
          }
          b=1;
      }
      /* J'affiche tous les membres du tableau... */
      for (i=0;i<=a;i++)
      {
          printf("\n%d est un nombre premier.\n",premier[a]);
      }
      printf("\n\n\n");
      system("pause");
      return 0;
}

Tout me semble juste, et pourtant.

Voici un aperçu de ce que cela me donne :

Saisir un nombre : 7

13959380 est un nombre premier.

13959380 est un nombre premier.

13959380 est un nombre premier.

Appuyez sur une touche pour continuer...

A première vue, je dirais qu'il me ressort le numéro mémoire du tableau...

Je suis perdu !

PS : je suis sur Windows 2000 Pro, utilisant Dev-C++.

**diogene** · 19/03/2008, 11h44

Code :

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

printf("\n%d est un nombre premier.\n",premier[i]);

D'autre part, il n'y a pas besoin de tester avec tous les nombres de 2 à nombre-1, il suffit de tester avec les nombres premiers déjà trouvés et rangés dans le tableau

**F.Margaine** · 19/03/2008, 11h51

[QUOTE=diogene;3065596]

Code :

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

printf("\n%d est un nombre premier.\n",premier[i]);

Erreur ridicule. Merci de me l'avoir fait remarquer.

D'autre part, il n'y a pas besoin de tester avec tous les nombres de 2 à nombre-1, il suffit de tester avec les nombres premiers déjà trouvés et rangés dans le tableau

Je ne comprends pas...

Ah sinon, mon programme ne marche vraiment pas !

Pourtant, le principe des nombres premiers et bien de n'avoir aucun diviseur autre que 1 et lui-même, n'est-ce pas?

Voici un exemple de ce que j'obtiens :

Saisir un nombre : 7

4 est un nombre premier.

6 est un nombre premier.

Appuyez sur une touche pour continuer...

Complètement à côté de la plaque...

**diogene** · 19/03/2008, 11h54

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
...
         if (b!=0)
          {
             premier[a]=nombre;
             a++;
          }
          b=1;
      }
      /* J'affiche tous les membres du tableau... */
      for (i=0;i<a;i++)
...

**F.Margaine** · 19/03/2008, 12h04

Pour le "for (i=0;i<a;i++)", c'était déjà modifié.

Pour la première modification, j'ai préféré mettre "if (b==1)".

Malheureusement, et je ne comprends vraiment pas pourquoi, cela n'a rien changé.

Et pardonnez-moi d'insister, mais je réitère ma demande de compréhension à propos de ce que vous m'avez dit...

D'autre part, il n'y a pas besoin de tester avec tous les nombres de 2 à nombre-1, il suffit de tester avec les nombres premiers déjà trouvés et rangés dans le tableau

Sur ce, je vous souhaite à tous bon appétit.

**diogene** · 19/03/2008, 12h18

J'ai testé avec ces modifications et ça marche.

Si le nombre n'est pas premier, il est divisible par un nombre premier plus petit que lui. Or ces nombres premiers sont rangés dans le tableau
(sauf 2 mais il suffit de le mettre en indice 0 et d'initialiser a à 1).

Code :

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

1
2
3
4
5
6
7
8
9
      premier[0] = 2;
      a=1;
....
          for (i=0;i<a;i++)
              if ((nombre % premier[i])==0)
              {
                 b=0;
                break;
              }

**F.Margaine** · 19/03/2008, 12h54

Envoyé par diogene

Si le nombre n'est pas premier, il est divisible par un nombre premier plus petit que lui.

J'ai des doutes. 14 n'est pas divisible par 13, alors que 13 est un nombre premier.

Enfin bon, je vais retester tout ça.

Edit : après avoir retesté (j'ai fermé et rouvert Dev-C++), ça a bien marché. Mea culpa, donc.

Je vous remercie de cette aide précieuse !

**diogene** · 19/03/2008, 13h01

Envoyé par F.Margaine

J'ai des doutes. 14 n'est pas divisible par 13, alors que 13 est un nombre premier.

mais il est divisible par 2 et 7 qui sont premiers!

**corentin59** · 19/03/2008, 13h01

Envoyé par F.Margaine

J'ai des doutes. 14 n'est pas divisible par 13, alors que 13 est un nombre premier.

Enfin bon, je vais retester tout ça.

Edit : après avoir retesté (j'ai fermé et rouvert Dev-C++), ça a bien marché. Mea culpa, donc.

Je vous remercie de cette aide précieuse !

mais il est divisible par 7 qui est premier et plus petit que 14 !!!

Le théorème dit que tout nombre entier N peut se décomposer en un produit de nombres premiers inférieurs ou égaux à N.

**F.Margaine** · 19/03/2008, 13h09

Oui enfin, votre théorême est un peu bancal !

Par exemple, pour 50, parmi les 15 nombres premiers avant, il n'est divisible que par un seul ! (2)

Faire un programme en se basant sur ça me semble bien ardu.

Dans l'exemple donné par diogene, ça finirait très vite par ne plus marcher!

Edit : hihihi, je lui ai fait chercher pour 1.000.000, ça fait au moins 5 minutes qu'il cherche !

**Thierry Chappuis** · 19/03/2008, 13h50

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
#include <stdio.h>
#include <stdlib.h>
 
#define N_ELEMS(array) ( sizeof (array) / sizeof *(array) )
 
void purge(void)
{
    int c;
 
    while ((c = fgetc(stdin)) != '\n' && c != EOF)
    {
    }
}
 
/* -tc- main() retourne un entier de type int, toujours! Par ailleurs, cet
   entier doit etre 0, EXIT_SUCCESS ou EXIT_FAILURE. */
int main(void)
{
    /* -tc- C'est une pratique recommandee de definir une seule variable
       par ligne. */
    int nombre;
    int n;
    int i;
    int premier[10000] = {0};
    int chiffre;
    int rv;
 
    do
    {
        printf("Saisir un nombre : ");
        /* -tc- Pour etre portable, il est necessaire de forcer l'affichage avec
           flush(). */
        fflush(stdout);
        rv = scanf("%d", &chiffre);
        /* -tc- A ce stade, il reste au minimum un caractere de fin de lign
           dans le tampon du flux d'entree standard. Il faut purger. */
        purge();
    }
    while (rv != 1);
 
    n = 0;
    if (chiffre > 2)
    {
        premier[n] = 2;
        n++;
    }
 
    for (nombre = 3; n < N_ELEMS(premier) && nombre < chiffre; nombre += 2)
    {
        int est_premier = 1;
 
        for (i = 0; est_premier == 1 && i < n; i++)
        {
            if (nombre % premier[i] == 0)
            {
                est_premier = 0;
            }
        }
 
        if (est_premier == 1)
        {
            premier[n] = nombre;
            n++;
        }
    }
 
    for (i = 0; i < n; i++)
    {
        printf("%d est un nombre premier.\n", premier[i]);
    }
 
    /* -tc- inutile sur tous les EDIs modernes et pas portable
    system("pause");
    */
 
    return 0;
}

Thierry

**diogene** · 19/03/2008, 14h03

Envoyé par F.Margaine

Oui enfin, votre théorême est un peu bancal !

Par exemple, pour 50, parmi les 15 nombres premiers avant, il n'est divisible que par un seul ! (2):

Parce que 50 n'est pas divisible par 5 ? C'est nouveau! De toute façon, il en suffit d'un. Dès qu'on en a trouvé UN, on sait qu'il n'est pas premier!

Faire un programme en se basant sur ça me semble bien ardu.

Dans l'exemple donné par diogene, ça finirait très vite par ne plus marcher!

Et si et ça sera bien plus rapide.

Edit : hihihi, je lui ai fait chercher pour 1.000.000, ça fait au moins 5 minutes qu'il cherche !

Ca ne devrait prendre qu'une fraction de fraction de microsecondes : Il est divisible par le premier nombre premier 2

**F.Margaine** · 19/03/2008, 15h01

Envoyé par diogene

Parce que 50 n'est pas divisible par 5 ? C'est nouveau! De toute façon, il en suffit d'un. Dès qu'on en a trouvé UN, on sait qu'il n'est pas premier!

Et si et ça sera bien plus rapide.
Ca ne devrait prendre qu'une fraction de fraction de microsecondes : Il est divisible par le premier nombre premier 2

Je comprends mieux dans quel sens il faut tourner cela. En partant du premier trouvé, et non du dernier, comme je l'avais pensé.

PS@Thierry : je regarderai le code plus tard.

**droggo** · 19/03/2008, 15h24

Fie,

Envoyé par F.Margaine

Oui enfin, votre théorême est un peu bancal !

Par exemple, pour 50, parmi les 15 nombres premiers avant, il n'est divisible que par un seul ! (2)

Faire un programme en se basant sur ça me semble bien ardu.

Dans l'exemple donné par diogene, ça finirait très vite par ne plus marcher!

Edit : hihihi, je lui ai fait chercher pour 1.000.000, ça fait au moins 5 minutes qu'il cherche !

Apparemment, tu cherches des nombres premiers sans vraiment savoir de quoi il s'agit.

**F.Margaine** · 19/03/2008, 15h26

Je n'ai jamais fait de maths dessus, tout ce que je sais à propos d'eux est qu'ils ne sont divisibles que par eux-même et le nombre 1. Mais vu que je n'avais rien à faire, l'idée m'est passée par la tête, et j'ai tenté.

Edit : je viens de voir pour les millisecondes de 1.000.000. Apparemment, vous n'avez pas compris ce que mon programme est censé faire. Il teste chaque nombre pour savoir s'il est entier. Il doit donc tester 999.997 nombres avant de passer à ce chiffre...

**diogene** · 19/03/2008, 16h06

Il doit donc tester 999.997 nombres avant de passer à ce chiffre...

J'avais bien compris, et c'est le reproche qu'on peut faire à ton code. Alors que dès la division par 2, on sait sans aller plus loin qu'il n'est pas premier. Tu fais donc 999.996 tests inutiles !

**F.Margaine** · 19/03/2008, 16h11

Envoyé par Thierry Chappuis

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
90
91
#include <stdio.h>
#include <stdlib.h>
/* -fm- Je ne comprends pas la syntaxe de ce define... */
#define N_ELEMS(array) ( sizeof (array) / sizeof *(array) )
 
/* -fm- Ni l'utilité de cette fonction. */
void purge(void)
{
    int c;
 
    while ((c = fgetc(stdin)) != '\n' && c != EOF)
    {
    }
}
 
/* -tc- main() retourne un entier de type int, toujours! Par ailleurs, cet
   entier doit etre 0, EXIT_SUCCESS ou EXIT_FAILURE. */
/* -fm- J'y ferai désormais attention. Je n'ai appris le C que récemment,
 * et l'on m'a dit que "main()" suffisait.
 */
int main(void)
{
    /* -tc- C'est une pratique recommandee de definir une seule variable
       par ligne. */
    int nombre;
    int n;
    int i;
    int premier[10000] = {0};
    int chiffre;
    int rv;
 
    do
    {
        printf("Saisir un nombre : ");
        /* -tc- Pour etre portable, il est necessaire de forcer l'affichage avec
           flush(). */
        fflush(stdout);
        /* -fm- Après une entrée de clavier, je croyais qu'il fallait 
         * faire fflush(stdin) ?!
         */
        rv = scanf("%d", &chiffre);
        /* -fm- Pourquoi ne pas simplement laisser la variable chiffre
         * pour s'occuper du while ?
         */
        /* -tc- A ce stade, il reste au minimum un caractere de fin de lign
           dans le tampon du flux d'entree standard. Il faut purger. */
        /* -fm- J'avoue ne pas avoir compris... */
        purge();
    }
    while (rv != 1);
 
    n = 0;
    if (chiffre > 2)
    {
        premier[n] = 2;
        n++;
    }
 
    /* -fm- Le fait que je n'aie pas compris le define au début
     * m'empêche de comprendre les paramètres de cette boucle.
     */
    for (nombre = 3; n < N_ELEMS(premier) && nombre < chiffre; nombre += 2)
    {
        int est_premier = 1;
 
        for (i = 0; est_premier == 1 && i < n; i++)
        {
            if (nombre % premier[i] == 0)
            {
                est_premier = 0;
            }
        }
 
        if (est_premier == 1)
        {
            premier[n] = nombre;
            n++;
        }
    }
 
    for (i = 0; i < n; i++)
    {
        printf("%d est un nombre premier.\n", premier[i]);
    }
 
    /* -tc- inutile sur tous les EDIs modernes et pas portable
    system("pause");
    */
 
    return 0;
}

Thierry

Merci de votre patience, si vous voulez bien m'aider !

**F.Margaine** · 19/03/2008, 16h14

Envoyé par diogene

J'avais bien compris, et c'est le reproche qu'on peut faire à ton code. Alors que dès la division par 2, on sait sans aller plus loin qu'il n'est pas premier. Tu fais donc 999.996 tests inutiles !

Non... Mon code est censé trouver AUSSI les nombres premiers qui sont AVANT 1M. Donc il doit tester TOUS les nombres pour savoir s'il y a d'autres premiers (et il y en a!).

**diogene** · 19/03/2008, 16h25

Envoyé par F.Margaine

Non... Mon code est censé trouver AUSSI les nombres premiers qui sont AVANT 1M. ...

Bien sur, sinon ce que je dis ne serais pas valable!

Donc il doit tester TOUS les nombres pour savoir s'il y a d'autres premiers (et il y en a!).

Mais pour le test du seul nombre 1000000, tu fais 999997 tests au lieu de 1. Et c'est le même phénomène pour tous les nombres que tu as testé avant 1000000 :
Pour tester 15, tu fais 12 essais alors que 2 suffisent
Pour tester 16, tu fais 13 essais alors que 1 suffit
Pour tester 17, tu fais 14 essais alors que 6 suffisent (et encore, on peut diminuer ce nombre)
etc.

**Thierry Chappuis** · 19/03/2008, 16h42

Envoyé par F.Margaine

Code :

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

1
2
3
4
#include <stdio.h>
#include <stdlib.h>
/* -fm- Je ne comprends pas la syntaxe de ce define... */
#define N_ELEMS(array) ( sizeof (array) / sizeof *(array) )

C'est une macro qui prend un tableau en argument et qui renvoie le nombre d'éléments de ce dernier. Le nombre d'éléments du tableau est obtenu en divisant la taille totale du tableau (en bytes) par la taille du premier élément.

Envoyé par F.Margaine

Code :

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

1
2
3
4
5
6
7
8
9
10
 
/* -fm- Ni l'utilité de cette fonction. */
void purge(void)
{
    int c;
 
    while ((c = fgetc(stdin)) != '\n' && c != EOF)
    {
    }
}

Cette fonction permet de purger le tampon du flux d'entrée standard en lisant un par un et en ignorant chaque caractère contenu dans ce tampon.

Envoyé par F.Margaine

Code :

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

1
2
3
4
 
/* -fm- J'y ferai désormais attention. Je n'ai appris le C que récemment,
 * et l'on m'a dit que "main()" suffisait.
 */

Non

Envoyé par F.Margaine

Code :

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

1
2
3
4
5
6
 
        printf("Saisir un nombre : ");
        fflush(stdout);
        /* -fm- Après une entrée de clavier, je croyais qu'il fallait 
         * faire fflush(stdin) ?!
         */

Il est interdit d'utiliser fflush() avec un flux entrant tel que stdin. Il s'agit d'un comportement indéterminé. Dans le code ci-dessus, on appelle fflush(stdout) pour forcer l'affichage de l'invite "Saisir un nombre : " qui ne se termine pas par un caractère de fin de ligne.

Envoyé par F.Margaine

Code :

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

1
2
3
4
5
 
        rv = scanf("%d", &chiffre);
        /* -fm- Pourquoi ne pas simplement laisser la variable chiffre
         * pour s'occuper du while ?
         */

Parce que ce qui nous intéresse ici, c'est de savoir si la conversion a pu être effectuée. scanf() renvoit le nombre de conversions effectuées avec succès.

Envoyé par F.Margaine

Code :

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

1
2
3
4
5
 
        /* -fm- J'avoue ne pas avoir compris... */
        purge();
    }
    while (rv != 1);

On effectue la saisie et on purge le tampon du flux d'entrée standard tant que la conversion échoue.

Envoyé par F.Margaine

Code :

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

1
2
3
4
5
6
 
 
    /* -fm- Le fait que je n'aie pas compris le define au début
     * m'empêche de comprendre les paramètres de cette boucle.
     */
    for (nombre = 3; n < N_ELEMS(premier) && nombre < chiffre; nombre += 2)

Et maintenant? Ais-je répondu à tes questions ?

Thierry

Emplacement mémoire tableau [Nombres premiers]

C

Discussions similaires

Partager

Partager