Nombre premier et factorisation

Commenter

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

S'inscrire maintenant

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.

Du même auteur (ADPro22)