Discussion :

[leppäkerttu]

Bonsoir,
j'ai écrit un petit programme avec 2 tableaux d'entiers non dynamiques, initialisés de la même façon. Jusqu'à 361 "cases", le programme fonctionne, à partir de 362 j'ai le message :

"Unhandled exception at 0x0041161f in PrimeNum_1.exe : 0xC0000005:Acces violation reading location 0x00142008"

Lorsque mes tableaux sont dynamiques, dès 200, j'obtiens ce message.
Mon PC n'est pas vieux, j'ai 2 Go de ram.
J'ai essayé avec des tableaux de long, la limite est toujours de 361.
? Je ne comprends pas où est le problème ?

[pascal.barbier]

Tu as probablement un problème de dépassement de capacité de ton tableau. Peut-on voir le code défaillant ?

[koala01]

Salut,

Heu, "unhandled exception", cela signifie, généralement, que tu n'a pas géré une exception qui aurait été lancée.

Maintenant, il faut savoir que les index, qu'ils s'agisse de tableaux alloués dynamiquement ou non, commencent à 0, et donc, que quand tu crées un tableau de N éléments, les index vont de 0 à N-1 (ce qui fait bel et bien N éléments )

Au vu de la suite du message (Acces violation reading location), il *semblerait* que ce soit là tout le problème: tu crées un tableau (ici) sous une forme proche de

Code :

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

tontype Tab[362];

et tu essaye d'accéder à

Code :

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

Tab[362]

alors que le dernier élément accessible est en fait

Code :

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

Tab[361]

Maintenant, pour être en mesure d'en dire plus, il nous faudrait un "code minimum compilable" qui nous permette de reproduire l'erreur

Nota: l'idéal, en C++, est souvent d'utiliser la classe std::vector<un type> qui permet de sécuriser très fortement l'utilisation de tableaux

[leppäkerttu]

Voici la bête :

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
 
#include "stdafx.h"
#include<iostream>
using namespace std;
 
void main(){
 
	int valid = 0;
	int paire = 0;
	const int size = 361; // limité à 361 au delà : bug
	int num = 1;
	int ix = 0;
	int i = 0;
 
	int tab1[size];
	int tab2[size];
	for (int j=0; j<size; j++){
		tab1[j]=0;
		tab2[j]=0;
	}
 
	while (num<4){
		tab1[ix] = num;
		tab2[ix] = tab1[ix];
		num++;
		ix++;
	}
 
	while (num<3000){
		if ( (num%2) == 0){
			paire = 1;
			num++;
		}
 
		if ( ( (num%2)!= 0) && (valid == 0)){
			paire=0;
			tab1[ix] = num;
			valid = 1;
		}
 
		if ((valid == 1)&&(paire == 0)){
			for (i=2; i< (ix-1) ; i++){
				if (valid ==1){
					if ( (tab1[ix]% tab2[i]) == 0){
						tab1[ix] = 0;
						num++;
						valid =0;
					}
				}
			}
			if (valid==1){
				tab2[ix] = tab1[ix];
				ix++;
				num++;
				valid = 0;
			}
		}
	}
	std::cout<<"The "<<(size-1)<<" first prime numbers are : "<<endl;
	for (int j=1;j<size;j++){
		std::cout<<tab2[j]<<endl;
	}
	std::cin>>ix;
}

Bon, c'est pas super optimisé, je sais , en fait, cela fonctionne tant que const int size est initialisée en dessous de 362. Donc, de 1 à 361, cela fonctionne, la sortie est correcte et tout.
Par contre, si const int size >= 362 alors là, j'ai le message de dépassement et de violation (VS 2005).
Mais sinon, cela fonctionne.
?

[Kujara]

Code :

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

1
2
int *tab1 = new int[size];
int *tab2 = new int[size];

Essaye ça pour voir ?

[yan]

Bonjour,
à quel endroit plante t'il?

[pascal.barbier]

Moi j'ai une autre erreur avec ce programme : sur la ligne

Code :

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

if ( (tab1[ix]% tab2[i]) == 0){

Une exception est levée parce que tab2[i] est nul

[pascal.barbier]

En plus, ton indice ix déborde largement de size parceque tu n'as pas mis de gardefou pour le limiter

[pascal.barbier]

Code :

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

1
2
int *tab1 = new int[size];
int *tab2 = new int[size];

Essaye ça pour voir ?

Pour quoi faire ? ce sont deux simples tableaux d'entiers, aucun besoin d'aller s'embêter avec des tableaux de pointeurs.
Quand le code marchera, notre ami leppäkerttu pourra envisager de passer à des tableaux dynamiques mais pas avant.

[Kujara]

Pour quoi faire ? ce sont deux simples tableaux d'entiers, aucun besoin d'aller s'embêter avec des tableaux de pointeurs.
Quand le code marchera, notre ami leppäkerttu pourra envisager de passer à des tableaux dynamiques mais pas avant.

Un tableau definit avec [] a une limite de taille, contrairement aux tableaux crées avec new.

Ok, on est loin de la limite, mais bon, on sait jamais, hein ^^

[pascal.barbier]

Ce que j'ai voulu dire dans mon post c'est que le problème n'est pas dans la taille du tableau mais plutôt dans une mauvaise utilisation (indice qui déborde).

Passer à des tableaux dynamique ne règlera aucun problème mais ajoutera à la confusion

[yan]

Code C++ :

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

while (num<3000 && ix<size){

serait mieux...
Ton bug viens que ton indice ix dépasse size-1 => violation de mémoire et bug aléatoire
[edit]
A zut, on t'as déjà résolu le problème

[Spout]

Nota: l'idéal, en C++, est souvent d'utiliser la classe std::vector<un type> qui permet de sécuriser très fortement l'utilisation de tableaux

Je suis d'accord tu peux le parcourir avec les itérateurs et eux ne dépasseront jamais la fin de ton tableau. Puis la taille peut changer au cours du programme.
A mon avis, tu auras moins de risques de passer à côté de choses comme le dépassement d'indexs avec les std::vector ...

[koala01]

Je suis d'accord tu peux le parcourir avec les itérateurs et eux ne dépasseront jamais la fin de ton tableau. Puis la taille peut changer au cours du programme.
A mon avis, tu auras moins de risques de passer à côté de choses comme le dépassement d'indexs avec les std::vector ...

Merci d'être d'accord avec moi

Sinon, ton code met déjà quelques problèmes en évidence:

std::cin et std::cout, avec une directive using namespace, donne l'impression d'en faire trop:

Cette directive permet d'éviter le préfixage de tout l'espace de nommage std.

Du coup, soit on utilise la directive (en dehors de tout fichier d'en-tête) et cin/cout, soit on n'utilise pas la directive et std::cin/std::cout

La fonction main renvoie d'office un int. Les deux prototypes admis sont

Code :

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

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    /*...*/
    return 0;
}
/* OU - OU - ou */
int main(int argc, char* argv[]
{
    /*...*/
    return 0;
}

Tu aurais fortement intérêt à utiliser les booléens pour les valeurs... booléennes, telles que pair et valide (qui n'ont en définitive comme valeur que "vrai" ou "faux").

L'avantage immédiat sera que tu pourra utiliser "true" ou "false"(voire un !valide pour indiquer que valide vaut "faux" ), ce qui rendra la lecture directement plus facile.

Enfin, j'ai l'impression que tu cherche la difficulté là où il n'y en a pas forcément...

Si j'ai bien compris, l'idée est de rechercher l'ensemble des nombres premiers.

Les math nous disent qu'un nombre est premier si il n'est divisible que par un et par lui-même.

Elles nous disent aussi que la valeur maximale à tester est... la racine carrée du nombre, étant donné que, pour un nombre quel qu'il soit, si tu peux le diviser par une valeur se trouvant en dessous de la racine carrée, tu obtiendra une valeur au dessus de la racine carré.

Un exemple avec 36 (racine carrée: 6)
36=2*18
36=3*12
36=4*9
36=6*6
(les autres valeurs tiennent de la permutabilité de la multiplication )

Le plus facile est donc, tout simplement, de faire une boucle qui effectuera les vérifications

Ainsi, le code

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
 
#include <iostream> // pour l'affichage
#include <vector> //pour utiliser la classe std::vector
#include <math.h> //pour utiliser sqrt
using namespace std; //pour la facilité d'écriture
 
int main()
{
    std::vector<size_t> tab; //il n'y aura que des entiers positifs...
    //ajoutons directement 0 et 1
    for(size_t i=0;i<2; i++)
        tab.push_back(i);
 
    //"soyons fous" demandons le nombre maximal à tester :D
    cout<<"introduisez le nombre maximal a tester :";
    size_t max;
    cin>> max;
    /* mettons nous au boulot */
    for(size_t i=2;i<=max;i++)
    {
        size_t racine=sqrt(i);/* prenons la racine carrée */
        bool divisible=false;
        size_t j=2; /* pas la peine de tester 1 ;) */
        /* pour gagner un peu de temps, pas la peine de
         * tester tous les nombres si on sait que ce n'est pas un nombre
         * primaire (qu'une des divisions a fourni un nombre entier)
         */
        while(j<=racine && divisible==false)
        {
            divisible=(i%j==0);/* on vérifie si le nombre est divisible par j*/
            j++;
        }
        if(divisible==false)
            tab.push_back(i);/* ajoute le nombre premier */
    }
    /* "YAPUKA" afficher les résultats */
    cout <<tab.size()<< " nombres premiers trouves entre 1 et"<<max
         <<endl<<"ce sont:"<<endl;
    for(size_t i=0;i<tab.size();i++)
        cout<<tab[i]<<endl;
    return 0;
}

J'ai réussi à faire en 41 lignes (commentaires compris) ce que tu a du mal à faire en 76... et même plus

Moralité: la solution la plus simple est toujours la moins compliquée... heu, la meilleure
[EDIT]Nota:sqrt renvoie normalement un nombre réel (float, double ou long double). Le fait de récupérer cette valeur dans un entier a pour seul effet de perdre la partie décimale, mais elle ne nous intéresse pas, et on peut donc le faire sans crainte (car le seul moment où elle nous intéressera sera le cas d'un nombre dont la racine carrée est... un entier, et que l'on teste cette valeur aussi )

[leppäkerttu]

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
 
#include "stdafx.h"
#include<iostream>
using namespace std;
 
void main()
{
begin:
	bool valid = false, paire = false ;
	int size = 0, max = 0, i =0, ix = 0, num =1 ;
 
	cout<<"Enter the number of prime numbers you want :"<<endl;
	cin>>size;
	cout<<"Enter the maximal value to check : "<<endl;
	cin>> max;
 
	int *tab1 = new int [size];
	int *tab2 = new int [size];
	for (int j=0; j<size; j++){
		tab1[j]=0;
		tab2[j]=0;
	}
 
	while (num<4){
		tab1[ix] = num;
		tab2[ix] = tab1[ix];
		num++;
		ix++;
	}
 
	while (num<max && ix<size){
		if ( (num%2) == 0){
			paire = true;
			num++;
		}
 
		if ( ( (num%2)!= 0) && (valid == false)){
			paire= false;
			tab1[ix] = num;
			valid = true;
		}
 
		if ((valid == true)&&(paire == false)){
			for (i=2; i< (ix-1) ; i++){
				if (valid == true){
					if ( (tab1[ix]% tab2[i]) == 0){
						tab1[ix] = 0;
						num++;
						valid = false;
					}
				}
			}
			if (valid== true){
				tab2[ix] = tab1[ix];
				ix++;
				num++;
				valid = false;
			}
		}
	}
	cout<<"The prime numbers, inbetween 0 and "<<max<<", are: "<<endl;
	for (int j=1;j<size;j++){
		cout<<tab2[j]<<endl;
	}
	delete tab1;
	delete tab2;
	goto begin;
}

J'avais les deux en stock (static et dynamique), mais c'était le même problème. Maintenant, les deux sont résolus : c'était bien ça :

Code :

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

(num<n && ix<size)

Complètement zappé le fait que ix puisse déborder de size !
pour std::vector je vais regarder ce que c'est.
MERCI BCP !

Sinon, koala01 je suis tes conseils :
- std::cout effectivement (avant c’était #include <iostream.h> et direct cout<< … transition laborieuse ).
- boolean, c’est noté, c’est plus clean, en effet.
- Pour le void, ça m’évite de noter return (elle ne retourne rien ici) c’est pas « bien » ?
- Pour l’histoire de la racine carrée, c’est très intéressant , je ne savais pas, je vais regarder (j’ai très vaguement entendu parler de l’histoire du logarithme pour l’espacement… mais c’est flou)
- Ton code, je vais le décortiquer
- Et la simplicité… Ahhh, la simplicité ^^ j’y travaille ^^

[koala01]

La norme précise que la fonction main renvoie un entier...

D'ailleurs, mon compilateur m'indique une erreur si j'essaye de définir main sous la forme de void main()

En plus, ce retour est renvoyé au système d'exploitation pour savoir comment s'est terminé le programme:

De manière générale: 0 réussite, autre chose: échec

Ceci dit, je réfléchissais justement au fait que tu voulais peut être trouver les N premiers nombres premiers, plutôt que les nombres premiers compris entre 0 et N

Dans ce cas, le code "le plus simple" est (44 lignes commentaires compris )

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> // pour l'affichage
#include <math.h> //pour utiliser sqrt
using namespace std; //pour la facilité d'écriture
 
int main()
{
    const size_t dim=10000;//a adapter selon tes envies/besoin:D
    size_t primary[dim];// notre tableau de nombre premier
    size_t last=2;//la première valeur qui sera testée
    // les deux valeurs "connues"
    primary[0]=0;
    primary[1]=1;
    /* une boucle pour remplir tous les éléments */
    for(size_t i=2;i<dim;i++)
    {
        /* il faut savoir si on a trouvé un élément à rajouter
         * au départ, ce n'est pas le cas :D
         */
        bool found=false;
        /* on boucle jusqu'à ce qu'on ai trouvé un nombre premier */
        while(!found) //c'est la meme chose que if(found==false):D
        {
            /* même logique que précédemment... on recherche les nombre premiers 
             */
            bool toadd=false;
            size_t racine=sqrt(last);
            size_t j=2;
            while(j<=racine && toadd==false)
            {
                toadd=(last%j==0);
                j++;
            }
            if(toadd==false)
            {
                found=true;
                primary[i]=last;
            }
            last++;/* on passe au nombre suivant */
        }
    }
    for(size_t i=0;i<dim;i++)
        cout<< primary[i]<<endl;
    return 0;
}

qui me trouve les ... 10 000 premiers nombres premiers et me les affiche en ... 1,031 secondes (10,750 secondes, affichage compris, pour les 100 000 premiers)

Pour ce qui est de la simplicité, je crois que le principal problème est de disposer d'une bonne méthode d'algorithmie...

Il faut commencer par "visualiser" correctement l'ensemble de la logique à appliquer pour résoudre le problème qui nous est posé, en étant sur d'éviter les différents "pièges à C" qui risquent de se présenter... Mais c'est un autre débat

Enfin, pour ce qui est de la racine carrée, il n'y a pas à s'inquiéter des logarithmes et autres "casse-tête" du genre ici...

On peut se contenter de savoir que si y=x*x, alors la racine carrée de y est x

Et pour décortiquer le code, ben, tu peux déjà, surtout, lire les commentaires (qui me semblent explicites) et n'hésite pas à demander un complément d'information si tu ne comprend pas tout

PS: les temps donnés sont ceux obtenus sur un "antique" athlon-xp 1800, avec 256Mb de ram

[koala01]

Pour info, chez moi, le dernier code que j'ai fourni (avec un tableau statique donc), et compilé en mode débug, fonctionne jusqu'à 521 090 éléments et plus dans le tableau sans affichage et fourni un résultat en 58,850 seconde

Chez moi, le fait de demander l'affichage sur plus de 520 620 éléments provoque une sortie sur erreur...

Je soupçonne les limitations dues à l'OS, au PC et au mode debug en ce qui concerne les tableaux statiques de provoquer cette erreur . Les valeurs sont donc fournies à titre indicatif uniquement

(l'affichage des 520 62 nombre premiers trouvés fait monter le temps d'exécution à ... 94,812 secondes... presque 40 secondes rien que pour l'affichage ): Le dernier nombre premier trouvé est 7 695 463.

Avec la première version du code, il était possible de monter à plus de 20 000 000 (pour un temps de calcul de 209 secondes, hors temps d'affichage et... 1 270 609 nombres premiers trouvés )

Je n'ai pas eu le courage d'effectuer des tests plus poussés (et surtout d'attendre les résulats ) mais tout laisse à penser que la limite serait de l'ordre de UINT_MAX (la valeur maximale admissible pour un entier non signé) ... Avec sans doute un temps de calcul se comptant en heures

[leppäkerttu]

C'est cool, merci

[Par contre, je suis vraiment obligée de rajouter std:: devant cout et cin, au moins pour chaque compilation "originale", sinon :
-> error C2065: 'cout' : undeclared identifier (mais si je les enlève ensuite, ça marche )]

Bref, j'ai essayé ton code, il est largement mieux, il rame moins (voire pas du tout, donc) que le mien (qui bizarrement prend 2 minutes avant de commencer à afficher , alors que le tien affiche directement). La racine, c'est une très bonne idée (et bien écrite en +, c'est clair)

Comment fais-tu pour savoir combien de temps, exactement, le calcul prend ?

[koala01]

A vrai dire, j'utilise l'IDE Code::blocks, et, quand on lance l'exécution depuis cet IDE, il indique le temps de travail et le statut de sortie

[leppäkerttu]

Thx