Résolution du crible d’Ératosthène

Version imprimable

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:

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;
}

04/01/2018, 09h18
Bousk

Est-on vraiment en C++ ? En dehors de l'utilisation de cout, on en est loin. :calim2:
04/01/2018, 19h29
ykamissokho

ban oui c du C++
04/01/2018, 19h53
bacelar

Citation:

ban oui c du C++

Bin tient, et depuis quelle version de la norme C++ on a le droit à des VLA ??? :aie:
std::array et std::vector sont tes amis.
les VLA, NON !!!
04/01/2018, 20h10
Bousk

Je ne vois aucun VLA :koi: juste des fuites mémoires.
05/01/2018, 11h27
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.
05/01/2018, 11h43
Seabirds

Citation:

Envoyé par Médinoc

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> ?
05/01/2018, 11h43
bacelar

Citation:

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 ??? :weird:
La routine de "nettoyage" est si spéciale que 1 n'est pas premier, WHAT ??? 8O

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

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)
05/01/2018, 14h31
prgasp77

Mais 1 n'est pas premier mon cher bacelar ;)
05/01/2018, 14h38
bacelar

Code:

Mais 1 n'est pas premier mon cher bacelar

Mais à l'époque d'Ératosthène, si. ;)
05/01/2018, 17h25
prgasp77

:ave:
C'est vrai.

Salut,

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

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
 
 
#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);
 
 
}

02/02/2018, 12h30
bacelar

Élégant, sauf la variable globale. :aie:
Et le nommage, :aie:
02/02/2018, 13h26
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"?
02/02/2018, 14h06
bacelar

Citation:

Envoyé par 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"?

Oui, ligne 25. ;)

en voici une autre version :

Code:

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...