Discussion :

[PyNub]

Bonjour,

Je voudrais savoir ce que vous pensez du code suivant :

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
#include<stdio.h>
 
int main(){
	int A=100000;/*valeur limite jusqu'où chercher les nb premiers */
	int tab[A];   /*le tableau dans lequel on va appliquer le crible */
	int i=0,j=0,k=0; /*j écriture dans tab, i lecture, k index de prem*/
	int prem[A];     /*résultat du traitement*/
	for(j=0;j<A-1;j++) tab[j]=j+2;/*initialisation de tab */
	tab[j]=0;	/* on met zéro dans la derniere case de tab pour se repérer*/
	while (tab[0]!=0){  	/*tant que tab n'est pas vide*/
		j=0,i=0;		/*raz de j & de i*/
		prem[k]=tab[0]; /*on ajoute la premiere valeur de tab dans prem */
		while (tab[i]!=0){ /*jusqu'à  la fin de tab*/
			i++;		/*on incremente l'index de lecture de tab*/
			if (tab[i]%prem[k]!=0){ /*on déplace les non multiples de...*/
				tab[j]=tab[i];/*la première valeur de tab...*/
				j++;	/*en début de tableau*/
			}
		}
		tab[j]=0;/*mise à  0 de la dernière case*/
		k++;            /*incrémente l'index du tableau de résultat :prem*/
 
	}
/*écriture du résultat*/
	prem[k]=0;
	printf("Nombres premiers jusqu'à  %i\n",A);
	for(k=0;prem[k]!=0;k++) printf("%i ",prem[k]);
	printf("\n");
	return 0;
}

J'ai vu sur certains forum que d'autres le font avec un seul tableau...
Sinon je ne sais pas calculer la longueur d'un tableau en C cette fonction existe-t-elle ?
mon programme est il propre ?
Il s'exécute en moins de 3 secondes. Pour moi c'est pas mal vu que cette fonction ci en python fait la même chose en plus de trente :

Code :

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

1
2
3
4
5
6
7
8
9
10
# -*- coding: utf-8 -*-
 
#Crible d'Eratosthène
def erat(lim):
  l=range(2,lim) 		#créé une liste l de 2 à  lim
  prem=[1] 			#crée une liste prem avec 1 
  while l:			#tant que l n'est pas vide faire
    prem.append(l[0])		#ajouter dans prem le premier nombre de l
    l=filter(lambda x:x%l[0],l)	#filtre de l tous les multiples du premier nombre de l
  return(prem)			#retourne prem

Merci.

[EpiTouille]

Tu devrait déjà donner des noms de variables explicites à tes variables car I,J,K et tab, demmande reflexion pour quelqu'un qui ne connait pas ton programme. Alors qu'une ligne de code bien faites, évite un commentaire. Pense que nous autres, ne connaissons pas ton code

[plxpy]

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
#include <stdio.h>
#include <stdlib.h>
 
// <combien> contiendra le nombre de nombres premiers retournes
// (i.e la taille du tableau retourne)
 
int *erat(size_t limite,size_t *combien)
{
    size_t  nb       = limite - 2;
    int    *tab      = (int *)malloc(nb*sizeof(nb));
    int    *premiers = (int *)malloc(nb*sizeof(nb));
    int     val;
    size_t  i,j;
 
    for (i=0;i<nb;i++) tab[i] = i+2;
 
    *combien = 0;
 
    while (nb)
    {
        premiers[(*combien)++] = val = tab[0];
	for (i=j=0;j<nb;j++)
            if (tab[j] % val)
                tab[i++] = tab[j];
        nb = i;
    }
 
    free(tab);
    premiers = realloc(premiers,(*combien)*sizeof(int));
    return premiers;
}
 
 
int main(int argc,char *argv[])
{
    int *premiers;
    size_t i, nb_premiers;
 
    premiers = erat(atol(argv[1]),&nb_premiers);
    for (i=0;i<nb_premiers;i++)
        fprintf(stdout,"%d\n",premiers[i]);
    free(premiers);
    return 0;
}

serait une meilleure traduction (dans le sens, plus dans l'esprit) de la fonction Python que tu donnes en exemple, d'ailleurs erronée, même si elle sort directement de wikipedia :

• 1 n'est pas un nombre premier (donc, ligne 6, on ne met pas 1 dans la liste, on la crée vide)
• range(2,lim) ne permet pas de tester lim : il faut mettre range(2,lim+1)

Après, question temps de calcul, ça ne rime pas à grand chose de comparer les deux langages sur cet exemple.
Python (sans employer les bibliothèques faites pour ça) n'est pas adapté pour faire ce genre de calculs. La différence est "normale".

ps : après (re)vérifications, seul le "range" est faux sur la page wikipedia. 1 n'est pas mis dans la liste. C'est juste dans ton exemple que le 1 est considéré comme premier

[PyNub]

1 n'est pas un nombre premier

1 n'est divisible que par lui même. Quel est la définition d'un nombre premier alors ?

range(2,lim) ne permet pas de tester lim : il faut mettre range(2,lim+1)

En effet j'ajoute que la fonction :

Code :

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

l=filter(lambda x:x%l[0],l)

ne marche pas avec python 3.1

serait une meilleure traduction (dans le sens, plus dans l'esprit) de la fonction Python

Je ne cherche pas forcément à traduire la fonction Python...

elle sort directement de wikipedia :

Oui je m'en suis servi avant tout pour vérifier mon programme.

Après, question temps de calcul, ça ne rime pas à grand chose de comparer les deux langages sur cet exemple.
Python (sans employer les bibliothèques faites pour ça)

Quelles sont ces bibliothèques ?

Sinon je débute et mon "vocabulaire" C est un peu limité. A quoi sert : malloc, sizeof, atol, realloc. Pourquoi utilisé fprintf au lieu de printf ?
Je ne suis pas très à l'aise encore avec les pointeurs c'est pour ça que je me suis contenté dans un premier temps de rester dans le main. Ton prog est très intéressant pour moi à ce niveau, je t'en remercie.

Tu devrait déjà donner des noms de variables explicites à tes variables

Oui c'est vrai d'où les commentaires... Personnellement je comprends mieux les commentaires que les noms de variables explicites, qui souvent, ne sont explicites que pour l'auteur.

Merci pour vos commentaires.

[droggo]

Hia,

1 n'est divisible que par lui même. Quel est la définition d'un nombre premier alors ?

Un nombre premier a 2 diviseurs, et 2 seulement.

et 1 n'en a qu'un ...

[PyNub]

Ok... autant pour moi d'autant que diviser par un n'a pas beaucoup de sens.
Mais on peut pas parler de C plutôt que de maths ou de Python ?

[Sve@r]

Sinon je ne sais pas calculer la longueur d'un tableau en C cette fonction existe-t-elle ?

Si ton tableau est un vrai tableau (avec des []), alors sizeof(tab)/sizeof(tab[0]) te donne sa taille. Mais si tu n'as qu'un pointeur sur son premier élément (comme toi avec tes malloc), alors pas possible. Mais pas utile non plus vu que tu es sensé maîtriser tes tableaux et donc connaitre leur taille en permanence...

Je voudrais savoir ce que vous pensez du code suivant :

Tu utilises 2 tableaux (en t'embêtant à recopier les nombres premiers de l'un dans l'autre) alors que tu peux te débrouiller pour n'en avoir qu'un seul (en utilisant astucieusement la valeur 0)...

Un exemple vite fait

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
unsigned int *erast(size_t nb)
{
	unsigned int *tab;
	size_t i;
	size_t j;
 
	// Initialisation (on commence par enlever un élément cause 1 pas premier)
	nb--;
	tab=malloc(nb * sizeof(unsigned int));
	for (i=0; i < nb; i++)
		tab[i]=i + 2;
 
	// Crible d'Erastothène - On met à 0 chaque multiple de n pris à partir de n2
	for (i=0; i < nb; i++)
	{
		for (j=tab[i]*tab[i] - 2; j < nb; j+=tab[i])
			tab[j]=0;
	}
 
	// A partir d'ici, le tableau contient soit des nombres premiers, soit 0
	// On décale tous les nombres vers la gauche
 
	for (i=0; tab[i]; i++);
	for (j=i; j < nb; j++)
	{
		if (tab[j] != 0)
		{
			tab[i]=tab[j];
			i++;
		}
	}
 
	// Juste au cas où (hasard), le i final pointerait vers un nombre premier (déjà copié à gauche) alors qu'il faut qu'il y ait 0
	tab[i]=0;
 
	// On renvoie le tableau des nombres premiers
	return tab;
}
 
int main(int argc,char *argv[])
{
	unsigned int *tab;
	size_t i;
 
	tab=erast(atoi(argv[1]));
 
	for (i=0; tab[i]; i++)
		printf("premier[%lu]=%lu\n", i + 1, tab[i]);
	free(tab);
}

Seul petite maladresse: comme je fais commencer le tableau à la valeur 2 (et non 1), je suis obligé de gérer et d'enlever au départ 1 au nombre d'éléments. Ca donne le bon résultat mais ça complexifie un peu l'algo (obligé de compter +2 d'un coté et -2 de l'autre et d'enlever 1 au nombre d'éléments alloués).

[PyNub]

comme toi avec tes malloc

Je n'utilise pas malloc... je ne sais pas ce que ça fait... à quoi sert malloc ?

Si ton tableau est un vrai tableau (avec des []), alors sizeof(tab)/sizeof(tab[0]) te donne sa taille.

Ok merci beaucoup Mais à quoi sert realloc et atol ?

Je vais essayer de le faire en un seul tableau quand j'aurai compris ton programme et toutes ces nouvelles fonctions. Merci pour l'exemple. Je me demandais comment renvoyer d'une fonction un tableau justement...

Merci beaucoup.

[Obsidian]

Je n'utilise pas malloc... je ne sais pas ce que ça fait... à quoi sert malloc ?

malloc() signifie « Memory Allocation ». Cela sert à demander au système (via la libC, dans un premier temps) de t'allouer un bloc mémoire dont tu indiques la taille souhaitée. Ce bloc existe tant que tu ne libères pas explicitement avec free(). C'est pour cela qu'il ne faut pas oublier de le faire, d'ailleurs.

Ok merci beaucoup Mais à quoi sert realloc et atol ?

rellaoc() sert à « réallouer » un bloc. Si un bloc n'est plus assez grand, tu peux demander à en faire modifier la taille. Si tu l'agrandis, le système le fait s'il le peut. Sinon il alloue un nouveau bloc et recopie le précédent dedans. Tu peux également le faire réduire pour libérer de la mémoire.

atol() signifie « ASCII to Long » et sert à lire un nombre écrit sous forme de chiffres dans une chaîne de caractère vers un int binaire exploitable dans ton programme. Vois également strtol().

[PyNub]

Merci beaucoup pour ces précisions

Sv@er je ne comprends pas la ligne26 dans ton programme :

Code :

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

for (i=0; tab[i]; i++);

que veut dire la condition tab[i] ? un erreur de frappe peut-être?

merci à tous pour vos réponses.

[Sve@r]

Tu peux également le faire réduire pour libérer de la mémoire.

Ca marche ça ? Il m'avait semblé lire qqpart que le realloc d'une taille plus petite n'avait aucun d'effet...

Je n'utilise pas malloc...

Désolé, erreur de lecture. C'est le code de plxpy qui emploi des malloc

Sv@er je ne comprends pas la ligne26 dans ton programme :

Code :

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

for (i=0; tab[i]; i++);

que veut dire la condition tab[i] ? un erreur de frappe peut-être?

Absolument pas. Est-ce que ton while l: en Python est une erreur de frappe ?
C'est la partie où je décale tous les nombres premiers vers la gauche. Il me faut d'abord trouver le premier emplacement libre, c'est à dire le premier emplacement où tab[i] vaut 0. Donc tant que tab[i] (sous-entendu différent de 0), j'incrémente i. Et cette boucle se suffit à elle-même d'où le point-virgule final. Quand la boucle se termine, i se trouve sur la première case à 0 du tableau.

Je me demandais comment renvoyer d'une fonction un tableau justement

Tu peux pas. Car, contrairement à Python, un tableau n'est pas un élément manipulable en C. Tu peux pas écrire if (tab1 == tab2). Bon en fait tu peux l'écrire mais ça ne fait pas ce que tu crois.
En fait, quand tu utilises la variable "tab" (nom du tableau), tu ne manipules que l'adresse de son premier élément => tab <=> &tab[0]
Et donc si tu écris une fonction qui renvoie un tableau, exemple

Code c :

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

1
2
3
4
5
6
fct(...)
{
     int tab[10];
     tab[...];
     return tab;
}

tu ne fais que renvoyer l'adresse d'une zone mémoire. Et en plus, cette zone étant automatiquement libérée lorsque la fonction se termine, ta fonction appelante reçoit l'adresse d'un truc qui n'est plus valide.

Seule solution: ta fonction alloue de la mémoire par malloc(). Dans ce cas, la mémoire est prise non pas dans la pile (zone des mémoires automatiques et volatiles) mais dans le tas (zone des mémoires statiques et permanentes).

Code c :

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

1
2
3
4
5
6
7
fct(...)
{
     int *tab;
     tab=malloc(10 * sizeof(int));
     tab[...];
     return tab;
}

Toutefois, il ne faut pas oublier, à un moment ou à un autre de ton code, de libérer la mémoire allouée (ce que je fais dans mon exemple en fin du main)