begin process at 2012 02 15 19:43:04
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths et Algorithmes

 > TEST DE PRIMALITÉ OPTIMISÉ

TEST DE PRIMALITÉ OPTIMISÉ


 Description

Sur ce site beaucoup de codes proposent des mméthodes pour tester la primalité d'un nombre, très peu sont optimisés.

En théorie, le test de primalité le plus efficace est celui qui repose sur une méthode dite de monte-carlo qui consiste à tester pour un nombre fixe de valeurs le petit théorème de fermat.

En partique, cette méthode entraine des calculs très volumineux qui aboutissent rapidement à des dépassements des varialbes.

Cette source présente une méthode simple, efficace et optimisée pour tester la primalité d'un nombre.

Source

  • import java.util.ArrayList;
  • import java.util.List;
  • /**
  • *
  • * Classe NombrePremier
  • *
  • * Cette classe regroupe un ensemble de méthodes
  • * statiques pour tester la primalité d'un nombre premier
  • *
  • * @author Julien
  • *
  • */
  • public class NombrePremier {
  • /**
  • * La méthode optimisée pour savoir si un nombre est premier
  • * On a exclu les nombres multiples de 2 et 3
  • * @param n : nombre à tester
  • * @return vrai si n est premier
  • */
  • public static boolean isPremier(int n){
  • boolean premier=(n!=1);
  • if(n!=2 && n!=3){
  • if(n%2==0 || n%3==0){
  • premier=false;
  • }
  • else{
  • int i=1;
  • while(premier && 6*i-1<=(Math.sqrt(n))){
  • if(n%(6*i+1)==0 || n%(6*i-1)==0){
  • premier=false;
  • }
  • i++;
  • }
  • }
  • }
  • return premier;
  • }
  • /**
  • * Une méthode optimisée pour lister les nombres premiers
  • * @param N : borne sup
  • * @return la liste des nombres premiers inférieurs à N
  • */
  • public static List<Integer> listePremierOptimisee(int N){
  • List<Integer> liste = new ArrayList<Integer>();
  • if(N>1){
  • liste.add(2);
  • }
  • if(N>2){
  • liste.add(3);
  • }
  • for(int n=5; n<N+1; n+=2){
  • boolean premier=true;
  • /** entre 0 et N, il y a a peu près N/ln(N) nombres premiers*/
  • int borne=(int)Math.floor((Math.sqrt(n))/Math.log(Math.sqrt(n)));
  • if(borne >= liste.size()){
  • borne--;
  • }
  • else{
  • while(liste.get(borne)<=(int)Math.sqrt(n)){
  • borne++;
  • }
  • }
  • int k=0;
  • while(premier && k<borne){
  • if(n%liste.get(k++)==0){
  • premier=false;
  • }
  • }
  • if(premier){
  • liste.add(n);
  • }
  • }
  • return liste;
  • }
  • } 
import java.util.ArrayList;
import java.util.List;

/**
 * 
 * Classe NombrePremier
 * 
 * Cette classe regroupe un ensemble de méthodes 
 * statiques pour tester la primalité d'un nombre premier
 * 
 * @author Julien
 *
 */

public class NombrePremier {
	
	
	
	/**
	 * La méthode optimisée pour savoir si un nombre est premier
	 * On a exclu les nombres multiples de 2 et 3
	 * @param n : nombre à tester
	 * @return vrai si n est premier
	 */
	public static boolean isPremier(int n){
		boolean premier=(n!=1);
		if(n!=2 && n!=3){
			if(n%2==0 || n%3==0){
				premier=false;
			}
			else{
				int i=1;
				while(premier && 6*i-1<=(Math.sqrt(n))){
					if(n%(6*i+1)==0 || n%(6*i-1)==0){
						premier=false;
					}
					i++;
				}
			}
		}
		return premier;
	}


	/**
	 * Une méthode optimisée pour lister les nombres premiers
	 * @param N : borne sup
	 * @return la liste des nombres premiers inférieurs à N
	 */
	public static List<Integer> listePremierOptimisee(int N){
		List<Integer> liste = new ArrayList<Integer>();
		if(N>1){
			liste.add(2);
		}
		if(N>2){
			liste.add(3);
		}
		for(int n=5; n<N+1; n+=2){
			boolean premier=true;
			/** entre 0 et N, il y a a peu près N/ln(N) nombres premiers*/
			int borne=(int)Math.floor((Math.sqrt(n))/Math.log(Math.sqrt(n)));
			if(borne >= liste.size()){
				borne--;
			}
			else{
				while(liste.get(borne)<=(int)Math.sqrt(n)){
					borne++;
				}
			}
			int k=0;
			while(premier && k<borne){
				if(n%liste.get(k++)==0){
					premier=false;
				}
			}
			if(premier){
				liste.add(n);
			}
		}
		return liste;
	}
}



 Sources du même auteur

Source avec Zip Source avec une capture FILTRE SUR LES COLONNES D'UNE JTABLE
Source avec Zip Source avec une capture REPRÉSENTATION GRAPHIQUE DE FONCTIONS ET OBJETS GÉOMÉTRIQUES
Source avec Zip Source avec une capture MENU CIRCULAIRE EN SWING
Source avec Zip Source avec une capture INVITE DE COMMANDES DOS
Source avec Zip DÉCOMPILER UN .CLASS JAVA AVEC JAD
Toutes les sources de Julien39

 Sources de la même categorie

IMPLÉMENTATION DE L'ENSEMBLE C AVEC JAVA par Scupper
CALCUL D'EXPONENTIEL ( PRÉCISION MODIFIABLE) par Scupper
Source avec Zip TRANSFORMATION D'UNE EXPRESSION ARITHMETIQUE (INFIXÉ) EN POS... par billatosco
PROBLÈME DES N-REINES par jojolemariole
Source avec Zip ARRAYMATRIX -MATRICE MULTIDIMENSIONELLE ET GÉNÉRIQUE- , IMP... par labandus
Toutes les sources de la catégorie Maths et Algorithmes

 Sources en rapport avec celle ci

NOMBRES PREMIERS PAR LE CRIBLE D'ERATOSTHÈNE VERSION OPTIMIS... par Virtuoooose

Commentaires et avis

Commentaire de jojolemariole le 15/02/2010 09:40:08

Salut,

Evidemment, tout dépend de l'utilisation, mais il me semblait qu'un algorithme probabiliste (donc pas sûr à 100%) donnait de meilleurs résultats. Ça pourrait être une alternative intéressante?

Commentaire de Julien39 le 15/02/2010 13:24:05 administrateur CS

Oui, c'est ce que j'ai expliqué dans l'introduction (rapidement), l'algorithme probabiliste est basé sur le test du théorème de fermat et c'est très efficace sur le papier puisqu'en seulement 50 itérations on peut tester la primalité d'un nombre.

Alors oui le mathématicien dira que l'algo ne donne pas une réponse sûre à 100%, mais avec 50 itérations, la probabilité que le programme se trompe est inférieure à la probabilité que l'ordinateur fasse une erreur donc, on peut l'utiliser comme on utiliserait un algorithme déterministe.

Le principal soucis est qu'il faut pour utiliser un algorithme probabiliste faire des calculs qui donnent des résultats très volumineux puisqu'ils sont exponentiels, il faut calculer a^N-1 avec a un nombre choisi au hasard entre 2 et N-1 et N le nombre premier à tester.
Ce qui donne pour savoir si 100 est premier un nombre à 200 chiffres, et ce qui entraine un dépassement des variable évident. Alors qu'avec un algo bien optimisé, il suffit de faire 4 calculs pour savoir si 100 et premier...

L'algorithme probabiliste peut être utilisé sur des nombres très très grands, qui dépasseraient largement les capacité des types long

C'est pour toutes ces raisons que je n'ai pas présenté d'algorithme probabiliste ici. C'est il est vrai bien dommage parce que les méthodes de monté carlo sont toujours plutot séduisantes sur le papier.



Sinon, il y a une autre méthode qui est utilisée par certains logiciels qui est de tester la primalité pour un grand nombre de valeurs mais pas des valeurs aléatoires, par exemple, on teste pour tout les nombres premiers entre 2 et 10^10, mais ca, ce n'est pas une méthode probabiliste bien qu'elle en soit proche, mais il n'y a aucun aléa dans cette méthode et donc les résultats sont très mauvais dès l'instant ù on dépasse un certain seuil.

Commentaire de pyo656 le 19/02/2010 19:15:22

Très intéressant :-)

Commentaire de Bacterius le 10/06/2010 13:38:40

Salut Julien39,
non, on n'a pas besoin de super grands nombres pour les algorithmes probabilistes. En utilisant l'algorithme de l'exponentiation modulaire, tu gardes les calculs aussi petits que le nombre premier à tester, et en plus tu fais l'exponentiation en un temps logarithmique en P.

Evidemment, pour tester des "gros premiers" il te faudra une librairie de grands nombres (même si Java fait déjà ça non ?) mais ça restera viable, tu pourras tester du 4096 bits en un temps raisonnable. Enfin normalement, je ne connais pas les performances du Java.

Cordialement, Bacterius !

Commentaire de Julien39 le 10/06/2010 17:09:44 administrateur CS

Ha oui, malin le logarithme, en plus c'est assez simple.

Java test la primalité mais je crois que le test est effectué jusqu'à un certain seuil (à vérifier)

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


iPod touch 3rd Generation (64 Go)
Entre 374€ et 379€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode
 
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 : 5,788 sec (4)

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)