Nombre premier et factorisation

Soyez le premier à donner votre avis sur cette source.

Snippet vu 5 038 fois - Téléchargée 38 fois

Contenu du snippet

Compilé avec Borland 5.5

Source / Exemple :


#include <iostream.h>
#include <math.h>
#include <conio.h>

unsigned long Diviseur(unsigned long n)
{
	unsigned long p = 1 ;
	unsigned long Res = n ;

	if((n%2)==0)
		Res = 2;
	else if((n%3)==0)
		Res = 3;
	else
	{
		while((Res==n)&&((6*p-1)<=sqrt(n)))
		{
			if((n%(6*p-1))==0)
				Res = (6*p-1) ;
			if((n%(6*p+1))==0)
				Res = (6*p+1) ;
			p++;
		}
	}
	return Res;
}

void Factor(unsigned long n)
{
	unsigned tmp1, tmp2 ;
	tmp1 = Diviseur(n) ;
	cout << tmp1 ;
	tmp2 = ( n /tmp1 ) ;
	while(tmp2!=1)
	{
		tmp1 = Diviseur(tmp2) ;
		cout << " * " << tmp1 ;
		tmp2 = ( tmp2 /tmp1 ) ;
	}
}

void main()
{
	unsigned long n ;
	clrscr() ;
	Presentation() ;

	cout << " Entrer le nombre a tester : " ;
	cin >> n ;
	cout << endl ;

	if(n==Diviseur(n))
		cout << "\t" << n << " est premier." << endl ;
	else
	{
		cout << "\t" << n << " n\'est pas premier.\n\n" ;
		cout << "\t" << n << " = " ;
		Factor(n) ;
	}
	cout << "\n\n\nAppuyez sur une touche pour continuer..." ;
	getch();
}

Conclusion :


Voici une façon de déterminer si un nombre est premier. Cet algorithme est basé sur le fait que tous les nombres premiers supérieurs à 5 peuvent s'écrire 6*p-1 ou 6*p+1. On n'a pas besoin de tester si tous les nombres impairs sont des diviseurs.
On décrit 5, 11, 17, ... ,6*p-1
et 7, 13, 19 , ... ,6*p+1

A voir également

Ajouter un commentaire Commentaire
Messages postés
9
Date d'inscription
vendredi 7 novembre 2003
Statut
Membre
Dernière intervention
19 novembre 2003

Tu peux encore simplifier pluss si tu savais.

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.