liste nombres premiers

Version imprimable

Salut à tous,

Je n'arrive pas à créer la liste des nombres premiers en C. Je l'ai faite il y a un certain temps, il me semble avec des pointeurs mais je n'ai pas envie de les utiliser et je ne comprends pas grand chose aux pointeurs. J'ai trouvé des programmes sur internet mais je les trouve longs. Je débute, mais je voudrais un code le plus concis possible. Je connais le crible d'Eratosthène (tester tous les nombres premiers jusqu'à sqrt(nombre_testé).

J'ai aussi fait une boucle en utilisant un tableau (c'est possible ?)

Mon programme me semble logique, mais il ne doit pas l'être !

Help me : je voudrais apprendre le C mais seul, c'est quand même difficile::cry:

Merci les gars et les gazelles

J'ai un warning : L15 : for (teste = 3 ; teste = nombre_choisi ; teste++)
Code:

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 #include <stdio.h> #include<math.h> int main(int argc,char *argv[]) { int nombre_choisi = 0; int liste_nombre_premier[1000000]={2}; int i = 0; int teste = 3; printf("Ce programme permet d\'afficher tous les nombres premier jusqu\'a un nombre que vous aurez choisi\n\n\n"); printf("Choisissez un nombre"); scanf("%d",&nombre_choisi); for (teste = 3 ; teste = nombre_choisi ; teste++) { while (teste%liste_nombre_premier[i]!=0 && liste_nombre_premier[i] <= sqrt(teste)) { i++; } if (teste%liste_nombre_premier[i]!=0) { break; } else { liste_nombre_premier[i] = teste; } } return 0; }
Erreur : Process terminated with status -1073741510 (9 minutes, 36 seconds)

13/03/2012, 00h01
pythéas

Citation:

Envoyé par zozoman

J'ai un warning : L15 : for (teste = 3 ; teste = nombre_choisi ; teste++)

Après le premier ';' se trouve la condition d’arrêt qui dans le cas présent est une affectation (donc toujours vraie la boucle ne devrait jamais s’arrêter)

Essaye :
for (teste = 3 ; teste == nombre_choisi ; teste++)

plus de warning mais bug

Merci pour ta réponse, le programme "tourne" : je n'avais pas encore vu ce détail.
Le programme tourne avec cette modification mais me donne juste la liste des nombres de 2 à nombre_choisi.

Code:

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
 
#include <stdio.h>
#include<math.h>
 
int main(int argc,char *argv[])
{
    int nombre_choisi = 0;
    int liste_nombre_premier[10000]={2};
    int i = 0;
    int teste = 3;
 
    printf("Ce programme permet d\'afficher tous les nombres premier jusqu\'a un nombre que vous aurez choisi\n\n\n");
    printf("Choisissez un nombre : ");
    scanf("%d",&nombre_choisi);
    printf("%d\t",liste_nombre_premier[0]);
 
    for (teste = 3 ; teste <= nombre_choisi ; teste++)
    {
        while (teste%liste_nombre_premier[i]!=0 && liste_nombre_premier[i] <= sqrt(teste))
        {
            i++;
        }
        if (teste%liste_nombre_premier[i]==0)
        {
            break;
        }
        else
        {
            liste_nombre_premier[i] = teste;
        }
        printf("%d\t",liste_nombre_premier[i]);
    }
return 0;
}

13/03/2012, 10h07
Bktero

Où est l'élimination des éléments non premiers ici ?

Ou alors :

Ton tableau n'est pas initialisé au début. Comment alors le parcourir et n'afficher que les nombres premiers puisque ce tableau contient..... des données plus ou moins aléatoires ?

EDIT : cette non initialisation explique surement que les while et if n'ont pas d'effet. De plus, je ne crois que A%B soit égal à B%A (ce n'est pas la même chose A congru à B [C]) et ici tes opérations me semblent inversées.
13/03/2012, 10h17
pythéas

En fait je suis étonné que ça compile, normalement sqrt devrait râler que tu lui passe un entier.
Sinon tu devrais afficher au maximum tes valeurs pour voir ce qui se passe à chaque itération, parce que là tout ça à l'air un peu confus.
13/03/2012, 10h46
Bktero
Je viens d'essayer de faire un programme affichant la liste et j'ai réussi. Mon code ne ressemble pas du tout à ton code d'ailleurs...

En revanche, j'ai compilé et je n'ai pas eu de problème avec sqrt. D'ailleurs, j'ai utilisé pow dans mon code et le compilateur ne râle pas, même avec -Wall et -Wextra (CodeBlocks, XP). Quand j'ai vu que les paramètres devaient être de type double, dans le man, je l'ai remplacé par une multiplication.

Pour le test, j'ai fait compilé ce bout de code :
Code:

1 2 3 4 5 i = 11; int b = pow(i,3); printf("\n\n\nb = %d",b); int a = sqrt(b); printf("\n\n\na = %d",a);
Et je n'ai pas eu de warning.... :calim2:

Essaye de remplacer ta fonction sqrt par une multiplication.
13/03/2012, 11h07
diogene

@pythéas

Citation:

normalement sqrt devrait râler que tu lui passe un entier.

Il n'y a aucune raison pour cela : l'entier est automatiquement converti en double qui devient l'argument de la fonction. La fonction renvoie un double.

@Bktero

Citation:

Essaye de remplacer ta fonction sqrt par une multiplication

Pour préciser, le test a*a <= P est plus rapide que a<= sqrt(P), à condition que a*a tienne dans un entier (int ici), donc si a n'est pas trop grand.
13/03/2012, 11h17
Bktero

1)Très logique pour le passage en paramètre, merci de le faire remarquer ! En revanche, le compilateur ne devrait-il pas mettre un warning lors de l'affectation d'un double dans int (puisque contrairement à la conversion de int vers double, il y a de grandes chances de perdre de l'information) ?

2)Très juste, encore merci pour la remarque ;)

Résolu et court

Il me manquait une boucle.

Peut on encore accélérer le programme et peut on augmenter la taille du tableau, j'ai trouvé des sites sans le programme ou la liste va au delà de plusieurs milliards ?

Merci à vous

Code:

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
 
 
#include <stdio.h>
#include <math.h>
#include <conio.h>
 
int main()
{
    int nombre_etudie; /* Nombre étudié*/
    int i; // Indice du nombre premier utilise
    int j; /* Indice du dernier nombre premier trouvé */
    int valeur_entree; // Valeur entrée
    int liste[200000]; /* Liste des J-1 nombres premiers */
    double NbEuclide; /* Nombre du crible d'Euclide */
 
    printf(" ******************************************************************************\n");
    printf(" *                                                                            *\n");
    printf(" *      PROGRAMME DE DETERMINATION DE TOUS LES NOMBRES PREMIERS DE 2 A N      *\n");
    printf(" *                                                                            *\n");
    printf(" ******************************************************************************\n");
 
 
    printf("\n\n\n\n\nEntrez une valeur N positive et superieure a 5 : ");
    scanf("%d",&valeur_entree);
    liste[0]=2;
    liste[1]=3;
 
    printf("\n\nListe des nombres premiers jusqu'a %d :\n %d\t%d\t",valeur_entree,liste[0],liste[1]);
    j=1;
 
    for (nombre_etudie=5;nombre_etudie<=valeur_entree;nombre_etudie+=2)
        {
            NbEuclide=floor(sqrt(nombre_etudie));
            i=0;
            while(nombre_etudie%liste[i]!=0 && liste[i]<=NbEuclide)
             {
                i++;
                if (liste[i]>NbEuclide)
                    {
                        j=j+1;
                        liste[j]=nombre_etudie;
                        printf("%d\t",liste[j]);
                    }
             }
        }
    getch();
    printf("\n\n");
    return 0;
}

13/03/2012, 14h07
diogene

@Bktero

Citation:

En revanche, le compilateur ne devrait-il pas mettre un warning lors de l'affectation d'un double dans int (puisque contrairement à la conversion de int vers double, il y a de grandes chances de perdre de l'information) ?

Il n'y a pas de pertes d'informations à proprement parler puisqu'une telle conversion change la valeur de la donnée de toute façon : on prend la partie entière du double. Ceci ne justifie pas un warning. Par contre, si cette partie entière est trop grande pour tenir dans l'entier, le comportement est indéfini. Le compilateur peut-il choisir d'émettre un warning pour une telle éventualité ? C'est discutable, car il y a beaucoup de situations analogues et on serait noyé sous une avalanche de warning non pertinents.

Par contre, il peut légitimement émettre un warning de perte de précision sur un changement double-> float ou même int-> float (avec int et float de même taille)