Discussion :

[alex2746]

Bonjour,
j'ai écris une fonction qui teste si un nombre est un nombre premier ou pas.
Elle fonctionne avec des petits nombres, mais quand je la teste avec des grands nombres, elle plante à l'exécution...

Le nombre est un unsigned int, je la teste donc avec la plus grande valeur possible: 4294967295 et ca plante à l'exécution... Pareil si je fais 4294967291, etc

La voici:

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
BOOLEAN premier ( unsigned int n)
{      	BOOLEAN verif;
	unsigned int i;
	verif=VRAI;
 
	if (n<2 || (n!=2 && n%2==0))
	    verif = FAUX;
	else
	{
	    i=n-1;
	    while (i>1){
	        if ((n%i)==0)
	        	verif = FAUX;
	        i=i-1;
	    }
	}
 
	return verif;
}

PS: BOOLEAN est un type que j'ai créé avec VRAI et FAUX, pas de soucis à chercher à ce niveau la!

[ram-0000]

Bonjour,
j'ai écris une fonction qui teste si un nombre est un nombre premier ou pas.
Elle fonctionne avec des petits nombres, mais quand je la teste avec des grands nombres, elle plante à l'exécution...

Tu as essayé avec un debugger parce que là, je ne voie aucune raison de faire crasher le programme.

Par contre, ton algo est faux (mais ne fait pas crasher)

Code :

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

1
2
3
4
5
6
7
8
	    while (i>1){
	        if ((n%i)==0)
	        {
	        	verif = FAUX;
	        	break;
	        }
	        i=i-1;
	    }

Dès que tu as trouvé une condition de divisibilité, tu sais que ton nombre n'est pas premier, donc tu peux quitter la boucle.

Pour info, une optimisation est encore possible en faisant intervenir la racine carrée (tu testes de 3 à racine carrée de ton nombre) alors que toi, tu testes de nombre - 1 à 1

[alex2746]

Je ne comprends vraiment pas mon problème...

J'ai essayé avec le débugueur, exécuter étape par étape, mais je ne peux pas appuyer 4000000000 de fois sur la touche, donc j'ai fais evoluer un peu mon i et puis j'ai changé la valeur du i en 50, et tout se passe bien...

Mais quand je l'exécute tout d'une fois, ca plante...

[SofEvans]

A tout hasard, pourrai-t'on recuperer quelque part comment est gerer l'operateur modulo ? Cela vient peut etre de la s'il ne gere pas les unsigned

[diogene]

Le code fonctionne chez moi sans planter (et trouve que 4294967291 est premier alors que 4294967295 ne l'est évidemment pas).

Si on prend en compte la remarque de ram-0000 sur le break, c'est une mauvaise idée de faire décroître i puisque le nombre a beaucoup plus de chances d'être divisible par un petit nombre que par un grand. Par exemple, il n'a aucune chance d'être divisible par i pour i> n/2.

SofEvans :

A tout hasard, pourrai-t'on recuperer quelque part comment est gerer l'operateur modulo ? Cela vient peut etre de la s'il ne gere pas les unsigned

Il gère tous les types entiers. On peut récupérer ces informations dans la norme :

6.5.5 Multiplicative operators
Syntax
...
Constraints
2 Each of the operands shall have arithmetic type. The operands of the % operator shall have integer type.
Semantics
3 The usual arithmetic conversions are performed on the operands.
...
5 The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.
6 When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.90) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.
...
90) This is often called ‘‘truncation toward zero’’.

[alex2746]

D'accord... Je ne comprends vraiment pas pourquoi chez moi il plante quand je mets 4294967295...
Quand je lance l'exécutable sur dos, il ne m'affiche rien et le curseur clique, je ne sais rien faire a part quitter..

J'utilise Eclipse comme IDE et je travaille avec un projet C ANSI.

[Sve@r]

Pour info, une optimisation est encore possible en faisant intervenir la racine carrée (tu testes de 3 à racine carrée de ton nombre) alors que toi, tu testes de nombre - 1 à 1

Même sans faire intervenir la racine (ce qui peut prendre du temps). On peut quitter la boucle dès que le résultat de la division devient plus petit que le diviseur (sous entendus si on fait varier les indices à partir de 3 vers le nombre et non l'inverse)

Une autre optimisation serait de faire varier les indices de 2 en 2 vu que les indices pairs sont définitivement éliminés...

Sinon concernant le pb de plantage, moi je tenterais de forcer le type "long" au lieu de "int" pour les variables...

[SofEvans]

Bon, d'apres les remarque, il semblerai que le probleme ne vienne pas du code ...
Peut etre cela vient-il du compilateur que tu utilise ? Est-ce vraiment un compilateur C et non C++ ?

[ram-0000]

Est-ce vraiment un compilateur C et non C++ ?

Et quand bien même, cela ne devrait pas être un problème