Nombre premier ou pas ? : verification par ce programme

Soyez le premier à donner votre avis sur cette source.

Vue 16 684 fois - Téléchargée 439 fois

Description

Ce programme passe par la méthode d'arithmetique étudiée en Terminale en Spécialité Maths, à savoir prendre la racine carré du nombre dont on veut verifier la primalité, et tester si le nombre originel n'est pas divisible par l'un des nombres premiers inferieurs a cette racine carré.
Mais étant donné mon niveau assez faible
j'ai ordonné a ce programme de tester tout les nombres inferieurs a cette racine carré sans exception.
Ainsi ce programme test, et si le nombre n'est pas premier donne un diviseur du nombre.
Voilà

Enjoy !

Ssaboum.

Source / Exemple :


#include <iostream.h>
#include <stdlib.h>
#include "stdio.h"
#include "math.h"
//Verification de nombres premiers

float main(void)
{
float a,x,b,p;
p=0;
x=1;
printf ("Entrez le nombre dont on va verifier la primalite :");
scanf ("%f",&a);
if (a<0) a=-a;
else b=sqrt(a);
printf ("il admet pour racine carre :%f\n",b);
do
{
x=++x;
//base du système:on cherche a savoir si le rapport a/x donne un entier
//ce qui revient a chercher si a est divisible par x
if (((a/x - floor(a/x))==0)&&(x!=a))
{
printf("ce nombre n'est pas premier et divisble par %f\n",x);
p=++p;
}
}
/* le problème est que maintenant(après avoir échangé le goto
par une boucle conditionnelle (avec bcp bcp de mal !!!)
le programme donne vraiment la liste de tous les diviseurs...
qu'ils soient premier ou non, pour ne pas saturer le code, je l'ai laissé
et puis au fond, c une fonctionnalité interressante,
le problème est que ça écrit beaucoup à l'écran,
quand le nombre à étudier est "grand" */

while (x<=b);
if (p==0) printf("Ce nombre est premier\n ");
      system("PAUSE");
      return 0;
}
//Fin du programme, n'hésitez pas a me contacter
//si vous pensez pouvoir m'aider à ameliorer ce programme

Conclusion :


Nota Bene pour les fonctions utilisées :
floor : arrondi à l'entier inferieur ainsi l'expression a/x - floor (blabla) equivaut a verifier si on a 1.2 - 1 = 0.2 ou si on a 1 - 1 = 0

A+

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
10
Date d'inscription
jeudi 1 juillet 2004
Statut
Membre
Dernière intervention
30 juillet 2004

Je confirme Metaldwarf a fait un programme utilisant une librairie pour la théorie des nombres avec la methode de miller rabin
bon g pas encore reussi a le faire marché :(
mais je ne sais pas très bien installé une nouvelle librairie non plus.
alors voilà qd meme le lien
http://www.cppfrance.com/code.aspx?id=21009

++

Ssaboum
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
41
autrement, j'ai trouvé de la doc en français sur miller rabin, et ici, tu as des sources expliquant ce principe... (moi, j'ai rien compris)
t'as metaldiarf qui a fait ça ici je crois...

miller rabin, c'est super rapide, c'est le principal avantage, mais c'est pas exact...

http://www.labri.fr/Perso/~betrema/deug/poly/premiers.html

voila, et y a des sources...
Messages postés
10
Date d'inscription
jeudi 1 juillet 2004
Statut
Membre
Dernière intervention
30 juillet 2004

voilà l'algorithme tant evoqué dans les commentaires !!!!
voilà la page originel (et donc en anglais sorry ;-))

http://www.cse.iitk.ac.in/news/primality.pdf


Enjoy

Ssaboum

"Ashita e to !!"
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Kirua il va pas pouvoir t'aider, j'y connais pas grand chose moi :/ suis au courant de c qui existe mais pour ce qui est de comprendre la preuve / coder l'algo j'ai pas d'expérience. l'algo probabiliste c'est rien à voir avec l'algo des 3 indiens. pour ce dernier, un coup de google sur algorithme 3 indiens nombre premier devrait donner un résultat je pense ^^ normalement c'est un document pdf publié par eux avec une explication mathématique (pr pas dormir) et puis surtout l'algo en pseudo-code, qu'il faut écrire en C/C++.
Messages postés
10
Date d'inscription
jeudi 1 juillet 2004
Statut
Membre
Dernière intervention
30 juillet 2004

merci pour ces commentaires, je vais changer le code en conséquence, je vais garder pour les remplacements :
-l'utilisation d'autre chose que des branchements (goto)
et je vais aussi essayer de chercher a propos de l'algorithme "crée par trois indiens" dont tu parles coucou747 (même si je l'avoue j'aimerai beaucoup beaucoup que kirua le mette !) sinon si je le trouve avant, je promet de le mettre en commentaire parole d'honneur !
je fais les changements de suite
A+

Ssaboum
Afficher les 14 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.