Discussion :

[boxydruM]

Bonjour, je n'arrive pas a créer une routine me servant à determiner si un nombre est premier ou pas.
La definition d'un nombre premier, c'est qu'il soit divisible que par 1 ou par lui meme. Mais je n'arrive pas à le mettre en forme...
C'est un algorithme :

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
fonction premier(a : Entier) : Boleen
variables
	boleen c
	entier b
        char x
debut
	c <- Vraie
	pour i de 2 à a faire
		tant que c = Vraie faire
			x <- a/i
				si x !== a
                                c = Faux
				finsi
		fintantque
	finpour
fin

merci!

Edit : changement de programme on m'a parlé du crible d'erathostene. Je vais m'y essayer.

[Goten]

C'est le forum C++ ici... pas algo :/


(par ailleurs sur wiki t'as tout plein d'algo pour ce genre d'application.)

[ram-0000]

C'est le forum C++ ici... pas algo :/

Je pense que justement le problème est l'implémentation en C++ d'un algo. Pour une fois qu'il y a un algo, saluons l'effort


quelques remarques sur ton algo

• "pour i de 2 à a faire", tu peux te contenter de "pour i de 2 à racine(a) faire"
• "x <- a/i" avec a, i et x entier, cela donne une division entière (3/2 = 1)
• Je ne comprends pas ce test (si c'est un test) "si x !== a"
• a, b, c, i, x sont des variables qui pourraient avoir un nom plus parlant (a NombreATester par exemple)

[Goten]

Oki, donc je rajouterais aux remarques de ram-0000, pourquoi le résultat de la division est stocker dans un char???

[boxydruM]

merci ram pour ton aide et tes conseils.
je modifie tout ça celon tes criteres.
Je continue et j'edit ce post avec le resultat.
Sur wiki je n'ai pas trouver encore d'algo ( je cherche actuellement )
Mais peut-on simplement creer un algo ou on test toutes les divisibilités du nombre, et s'il n'y a que lui meme ( j'exclue 1 ) alors il est premier.
Mon test justement sert à rien, en fait il est incomplet car j'essaye dans ce passage de determiner s'il a un diviseur inferieur à lui meme. Il ne serait donc pas premier.

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
fonction premier(NombreATester : Entier) : Boleen
variables
	boleen resultat
	entier x
debut
	resultat <- Vraie
	pour i de 2 à NombreATester faire
		tant que resultat = Vraie faire
			x <- NombreATester/i
				si x est un entier !== 1 alors
					resultat = Faux
				finsi
		fintantque
	finpour
	retourner resultat;
fin

maintenant c'est comment traduire 'si x est un entier'
c'est possible?
ou je dois faire autrement ?

[boxydruM]

Voila je penses avoir trouver une bonne methode.
Dites moi ce que vous en pensez :

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
fonction premier(NombreATester : Entier) : Boleen
variables
	boleen resultat
	entier x
debut
	resultat <- Vraie
	pour i de 2 à NombreATester faire
		si NombreATester(modulo i) == 0 alors
			si NombreATester/i > 1 alors
				resultat <- Faux
			finsi
		finsi
	finpour
	retourner resultat;
fin

[hiura]

quelques remarques sur ton algo

• "pour i de 2 à a faire", tu peux te contenter de "pour i de 2 à racine(a) faire"

ça réduira le temps de calcul.

maintenant c'est comment traduire 'si x est un entier'
c'est possible?

Tout est possible.
Pour savoir si une division donne un nombre entier il "suffit" de tester si le reste de la division est nulle.

[ram-0000]

Une petite modification encore :

Code :

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

1
2
3
4
5
	pour i de 2 à racine(NombreATester) faire
		si NombreATester(modulo i) == 0 alors
			resultat <- Faux
		finsi
	finpour

Tu peux faire cette simplification car i (que l'on pourrait renommer en 'diviseur' par exemple ) ne vaut jamais 1 (il commence à 2) et NombreATester/i ne vaut jamais 1 vu que tu boucles jusqu'à racine(NombreATester) et pas NombreATester

[Goten]

Tu peux aussi tester une fois le diviseur 2, puis après ne tester que les nombres impairs .