Test de primalité optimisé

Commenter

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

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 (cs_Julien39)