Discussion :

[ykamissokho]

bonjour
je veux afficher l'ensemble des nombre premier inférieur à un entier n par le Crible d’Ératosthène et j'ai un problème quand n dépasse 15 pouvez vous m'aider voila mon code:
merci d'avance

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
#include<iostream>
#include<math.h>
using namespace std;
// je cree un tableaux dynamique 
int* tab(const int taille)
{
	int* tab = new int[taille];
	return tab;
}
 
int main()
{
	int i, j,n,compteur=1;
	int k = 0;
	cout << "saisir le reelle n:  ";
	cin >> n;
	int * tabl = tab(n);
	for (i = 0; i < n; i++)
		tabl[i] = i;
	for(i=2;i<sqrt(n);i++)
	{ 
		for (j = i+1; j < n; j++)
		{
			if (i != j)
			{
				if (j%tabl[i] == 0)
				{
					compteur=compteur+1;
					tabl[j] = 1;
 
				}
			}
		}
	}
	int *newtab = tab(n - compteur);
	for (i = 1; i < n; i++)
	{
		if (tabl[i] != 1)
		{
			newtab[k] = tabl[i];
			k++;
		}
 
	}
	cout << "\nles nombres premier sont au nombre de "<<n-compteur<<"\n";
	for (i = 0; i < (n - compteur); i++)
	{
		cout << newtab[i];
		//system("pause");
	}
 
	cout << "\n\n";
 
 
	return 0;
}

[Bousk]

Est-on vraiment en C++ ? En dehors de l'utilisation de cout, on en est loin.

[ykamissokho]

ban oui c du C++

[bacelar]

ban oui c du C++

Bin tient, et depuis quelle version de la norme C++ on a le droit à des VLA ???
std::array et std::vector sont tes amis.
les VLA, NON !!!

[Bousk]

Je ne vois aucun VLA juste des fuites mémoires.

[Médinoc]

Par contre, c'est néanmoins vrai que ce code est plus du "C avec new et cout"* que du "vrai C++", bien qu'il soit techniquement un code qu'un compilo C++ accepte.

Un bon crible d’Ératosthène utiliserait un vecteur de booléens pour indiquer quels nombres ont été "vus": Il est inutile de mémoriser les nombres eux-mêmes dans le tableau du crible, vu que leur valeur est égale à leur index (ou leur index moins 1 etc., selon la façon dont est organisé le tableau).

*Incidemment, c'est comme ça qu'on nous avait "initié au C++" en BTS... j'ai dû tout désapprendre quand j'ai appris le C++ proprement dit.

[Seabirds]

Un bon crible d’Ératosthène utiliserait un vecteur de booléens

Je croyais que les std::vector<bool> étaient à éviter (dans le bouquin de Scott Meyers, Effective STL), et qu'il valait mieux utiliser std::deque<bool> ?

[bacelar]

Je ne vois aucun VLA juste des fuites mémoires.

Ok pour le VLA, j'ai regardé trop rapidement.
Mais si on regarde le code lui-même, sans prendre en compte la pléthore de mauvais usages, c'est du grand nimportnawak.

On entre une valeur, elle ne fera pas partie de l'intervalle de recherche, bof, mais bon, ça esquive le "<" au lieu du "<=" de la ligne 20.

Le tableau commence à tab commence à 0, tab[0] == 0. WHAT ???
La routine de "nettoyage" est si spéciale que 1 n'est pas premier, WHAT ???

C'est quoi cette condition toute pété ligne 24 ???

Ligne 26, on se sert de "tab" à la fois comme tableau d'entré et de sortie, en sachant qu'il est complètement inutile en entré et qu'en l'utilisant en entré, cela transforme le premier nombre nom premier, 4, en diviseur de tous les nombres.

Dans les faits, vous n'implémentez absolument pas le crible d'Ératosthène, désolé.

En résumé, utiliser un papier et un crayon, c'est pas surfait, et le débuggeur est notre ami.

(Mais putain, ce code C++ archaïque, ça pique les yeux)

[prgasp77]

Mais 1 n'est pas premier mon cher bacelar

[bacelar]

Code :

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

Mais 1 n'est pas premier mon cher bacelar

Mais à l'époque d'Ératosthène, si.

[prgasp77]

C'est vrai.

[Barbasol]

Salut,

J'ai fait le test en récursif (avec l'algorithme donné sur Wikipedia) :

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 <iostream>
#include <vector>
 
using namespace std; 
 
vector <int> v; 
 
void affichageVecteur (){
 
    for (int i=0; i<v.size(); i++)
        cout <<  v[i] << " ";
 
} 
 
void eratosthene (int p, int d){
 
    if (v[0] * v[0] > v[v.size()-1])
        affichageVecteur();
    else {
        cout << v[0] << " ";
        for (int i=0; i<v.size() ; i++)
            if (v[i]%p == 0)
                 v.erase(v.begin() + i); 
        eratosthene (v[0], v[v.size()-1]);    
    }
 
}
 
 
 
int main () {
 
    int p = 2;
    int d = 1000; 
 
    for (int i=p; i<=d; i++)
        v.push_back(i);
 
     eratosthene(p, d);
 
 
}

[bacelar]

Élégant, sauf la variable globale.
Et le nommage,

[Médinoc]

J'ai du mal à voir l'intérêt de faire ça en récursif. Cela évite-t-il des passes inutiles sur des nombres déjà "marqués"?

[bacelar]

J'ai du mal à voir l'intérêt de faire ça en récursif. Cela évite-t-il des passes inutiles sur des nombres déjà "marqués"?

Oui, ligne 25.

[Invité]

en voici une autre version :

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
#include <cstdlib>
#include <fstream>
using namespace std;
int main() {
  {
    ofstream f("crible.hs");
    f << "premiers = crible [2..] \n"
      << "  where crible (p:xs) = p : crible [x | x <- xs, x `mod` p /= 0] \n"
      << "main = do \n"
      << "  putStrLn \"Entrez n :\" \n"
      << "  line <- getLine \n"
      << "  let n = read line :: Int \n"
      << "  print $ takeWhile (<n) premiers \n";
  }
  system("runghc crible.hs");
  return 0;
}

il faut juste installer aussi le compilateur haskell mais après tout c'est à peu près autant du C++ que la première version proposée...