Test de primalité optimisé

Soyez le premier à donner votre avis sur cette source.

Snippet vu 7 385 fois - Téléchargée 18 fois

Contenu du snippet

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 / Exemple :


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;
	}
}

A voir également

Ajouter un commentaire Commentaires
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
355
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)
Messages postés
3793
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
3 juin 2016
9
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 !
Messages postés
34
Date d'inscription
lundi 11 septembre 2006
Statut
Membre
Dernière intervention
19 février 2010

Très intéressant :-)
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
355
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.
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
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?

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.