begin process at 2012 02 10 13:59:54
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > NOMBRE PREMIER OU PAS ? : VERIFICATION PAR CE PROGRAMME

NOMBRE PREMIER OU PAS ? : VERIFICATION PAR CE PROGRAMME


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Niveau :Débutant Date de création :01/07/2004 Date de mise à jour :05/05/2007 14:40:40 Vu / téléchargé :13 661 / 348
Auteur : ssaboum

Ecrire un message privé
Commentaire sur cette source (14)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
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

  • #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
#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+



 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !
  • Nombre premier(2ème version).exeTélécharger ce fichier [Réservé aux membres club]23 040 octets

Télécharger le zip


 Historique

30 juillet 2004 11:01:23 :
Bugs de la dernière version corrigés: **-:Bug au niveau de petit nombre premier genre 2, où il affichait que 2 était divisible....par 2 et que donc il n'etait pas premier....facheux. Le bug venait du fait que je pensais qu'étant donné que je partait des nombres inferieur a la racine carré du nombre, ce cas n'arriverait jamais. Commez quoi ...tt arrive. La correction se fait maintenant en intégrant dans les condition que x different de a. Bugs ou plutôt effet secondaire de cette version : vous avez maintenant la liste des diviseurs (premiers et non-premiers :!) du nombre dont vous voulez verifier la premialité... Bon par definition c'est pas trop génant si c un nombre premier mais sinon, s'il est grand ca peut vous remplir une page entière... Si quelqu'un veut que je l'enleve ou mieux connaitrai : le CMN (Changement Minimum Nécessaire) qui me permettrait d'enlever ou de mettre à volonté cette fonctionnalité Je suis preneur ! Bye
05 mai 2007 14:40:41 :
correction de bugs de programmation

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de elinep le 01/07/2004 10:31:17

Salut, une petite optimisation super simple au lieu de faire x++, tu incremente de 2 car une fois qu tu as teste la divisibilite par 2 cela ne sert a rien de tester par 4,6,8...donc tu pars de x=2 et tu fais x=x+2.

Commentaire de ssaboum le 01/07/2004 13:15:31

Ouais merci pour ce conseil, mais en fait je crois que ce qu'il faudrait pour arriver a mettre a profit chaque boucle c que x devienne a chaque boucle un nombre premier different inferieur a la racine carré de a....
Si tu sais comment faire informe moi :-)
A+

Ssaboum

Commentaire de elinep le 01/07/2004 14:14:47

halala je serais celebre si je pouvais te donner une formule magique donnant les nombres premiers dans l'odre :)
C'est un truc qu'il reste a decouvrir, a l'heure actuelle c'est pas possible...
Sinon je crois savoir qu'il existe un algo plus performant pour tester si un nombre est premier, il utilise la formule "p^n congru à p[n]" (je crois que c'est ca la formule je suis pas sur :p)
C'est assez recent comme algo, je sais pas si on peut trouver des infos dessus...
Dans l'espoir de ne pas avoir dit trop de betise :D

Commentaire de Kirua le 13/07/2004 09:52:58

renseigne toi sur le crible d'eratosthène, ça prend 10 lignes à programmer, et ca te permettra daccelerer les choses. (desole pr lecriture, je viens de passer 12 jours sur un qwerty, je nai plus lhabitude des apostrophes et des accents :p)

remarque que pr les grands nombres (plusieurs dizaines de chiffres comme pr le RSA (en fait plusieurs centaines)) il faut utiliser un algo probabiliste, et ca, ben euh, euh, une autre fois :p

Commentaire de nico4486 le 15/07/2004 22:43:31

il me semble qui ya une erreur:
if (a<0) a=-a;
else b=sqrt(a);
printf ("il admet pour racine carre :%f\n",b);

je le corrigerai en enlevant le "else"


Commentaire de ssaboum le 15/07/2004 22:52:48

c possible tu as raison mais le else ne change pas grand chose dans le code, sauf perdre "du temps"
mais là ca se jout a la mililililililiseconde je pense que l'on peut s'en passer ;-)
mais merci

Commentaire de brenntengel le 26/07/2004 17:02:43

C'est pas mal de tout.
Mais un conseil :L'utilisation de goto et DECONSEILLER !!(Les branchement )
utilise do  while   c'est mieux !!

Commentaire de toughwhale le 26/07/2004 20:39:34

ton source est jolie c'est bien mais ton code est a peut pres longue tu peux l'ameliorer pour etre 8 a 10 ligne
bien programme.

Commentaire de coucou747 le 29/07/2004 19:18:03 administrateur CS

le crible d'ératostène ne doit pas être utilisé dans ce cas la, car ce cryble sert a connaitre tout les nombres premiers infèrieurs a un autre nombre, or ici, tu ne cherches qu'un nombre premier...

les nombres sous la forme : n=2^p-1 ou p est premier sont apelés nombres de mercènes, mais ils sont aujourd'huit inutilisablezs (le plus grand nombre premier trouvé a l'heure actuelle est un nombre de mercène) Ces nombres sont particuliers, donc, si tu cherches a être la personne qui trouvera le prochain plus grand nombre premier découvert, tu peux l'utiliser, mais si tu cherhces a crypter un fichier, c'est totalement inutile...

Pour les nombres premiers, tu as miller rabin qui est pas mal, dsl, je ne connais ce tes que de nom...

Tu as aussi un test créé par trois indiens (je crois) qui est du niveau terminale pour le mettre en place, mais d'un autre niveau pour le comprendre... (diconc cimplement que je ne suis pas rendu)...

Kirua, tu en avais parlé, tu avais dit que tu avais un SVJ qui donnait l'algo en pseudo code, je suis prenneur si tu veux bien le mettre en commentaire, ça lui permetra de modifier son programme... (et je vais faire pareil que lui, mais avec des nombres un peu plus grand...)

Ton test est largement suffisament optimisé pour des nombres codés sur 32 bits, je ne l'ai pas testé, mais j'ai fait tourné un algorythme basé sur le même principe, et j'arrivais à avoir plusieurs nombres par secondes...

Bon début, mais pour ceci, tu peux facilement te passer de math.h ne pas mettre de goto etc...

par exemple, a la place de
if (b==sqrt(a));
tu mets
if (b*b==a)

Commentaire de ssaboum le 29/07/2004 19:32:27

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

Commentaire de Kirua le 30/07/2004 22:46:08

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

Commentaire de ssaboum le 30/07/2004 23:24:37

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 !!"

Commentaire de coucou747 le 31/07/2004 01:17:56 administrateur CS

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

Commentaire de ssaboum le 31/07/2004 11:31:21

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

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


Samsung Galaxy S
Entre 529€ et 529€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Beautiful woman in a bikini meditating on the beachPhoto Framed Landscape Image of Monument Valley
Photo Marais Salants d'Aigues-Mortes (30220), Gard 

Visiter la photothèque
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 2,964 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)