Nombre Premier

Question

Bonjour,

Je voudrais savoir comment on peut faire pour verifier qu'un nombre est premier facillement ? 

Merci de votre aide 

@+++

DOS

kirua12 · Answer

Salut,

sur C/C++ code sources, il y a une petite source qui fait ça. T'as plus quà traduire en Java.
http://www.cppfrance.com/code.aspx?ID=10491

CHKDSK2K · Answer

Yo kirua12

Je voudrais savoir si tu n'as pas une methode plus simple je vx dire avec moin de calcul a éffectuer car je vais travailler sur des grands nombre pas du style 14241 donc il faut diminuer le plus possible les calcul ...  

@+

DOS

kirua12 · Answer

Désolé, je ne suis pas une bête en maths.
Mais je pense pas que tu trouveras mieux. Les traitements sur les nombres premiers demandent pas mal de calcul.
Là je laisse la place aux matheux !!!  :)

cs_Dobel · Answer

Salut

ya la méthode isProbablePrime de la classe BigInteger
extrait de la doc :
public boolean isProbablePrime(int certainty)
Returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is <= 0, true is returned. 

Parameters:
certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2certainty). The execution time of this method is proportional to the value of this parameter. 

mais ca c'est pour les paresseux
;-p

pour les types qu'en ont :
algorithme de Rabin Miller
attention : algorithme probabiliste

en gros pour tester p :

calculer b où b est le nombre de fois que 2 divise p-1 (2^b
est la plus grande puissance de 2 qui divise p-1).
1. On prend un nombre aléatoire a inférieur à p.
2. Poser j=0 et z=a^m mod p.
3. Si z=1 ou si z=p-1 alors p peut-être
premier.
4. Si j>0 et z=1 alors p non premier.
5. Poser j=j+1. Si j tout plein d'algorithmes)

A+

DOBELIOU

cs_GodConan · Answer

GodConan :clown) 

ben ;o) c un des dada favori  de pas mal de matheu la decouvert du +  grd nombre premier possible ;o) 

autrement la meilleur soluce (actuelle ) au nivo rapidite est de stoker une librairie(base) de tous les nombre premier connu(i en a un bon packer deja) ;o) et apres c facil puis si ton nombre est tro grd ben tu fait les calculs ;o) m enfin c pas si lon ;o) sa depassera pas les keke jour ;o) (la on parle de TRETRETRES grd nombre)

GL

++

CHKDSK2K · Answer

Hello, 

dit es ce que vous pouvez me donner plus d'information sur isProbablePrime car sur google je ne trouve pas d'information et en anglais je ne suis pas assez fort pour comprendre ... alors pourriez vous m'aider svp

THX

cs_Dobel · Answer

SLUT'

dans l'ordre : 

pour créer le BigInteger : 
par exemple en passant par BigDecimal
BigInteger p = (new BigDecimal((double) p)).toBigInteger();
ou alors (plus recommandé)
BigInteger p = new BigInteger("1234567897897");
c'est à dire:
BigInteger p = new BigInteger((new Integer(p)).toString());

(il n'y a pas de constructeur qui prend directement un int en paramètre -> c'est pas le but de la classe :-p)

ensuite
int certainty =  30;//par exemple
boolean test = p.isProbablePrime(certainty);

si test==true, alors la probabilité que p soit réellement premier dépasse 1-(1/2)^certainty
pour 30, la proba depasse .999999999068677
-> c'est pas trop mal je pense ;-p

bien sur, plus certainty est élevé, plus le temps de calcul est long

pitite remarque : 
si tu n'utilise pas de nombre trop grand (c'est à dire si les int suffisent donc p<2^31-1)
utilise plutôt le Rabin Miller du site que je t'ai indiqué (copier coller ;-p): 
Je pense que tu gagnes du temps car tu n'as pas à creer le BigInteger

A+
DOBELIOU

CHKDSK2K · Answer

Merci pour les informations j'ai capich lol :)
mais j'ai une autre question ...

comment verifier si un nombre a une virgule ? 

DOS

cs_GodConan · Answer

GodConan :clown) 

c pas clair comme question...
si tu veu savoir si un nombre est entier il a plusieur teknik ;o)

l une delle consiste a regarder regarder si la parti entier du nombre et egal au nombre lui meme ;o) ... 

++

CHKDSK2K · Answer

ouais c'est pas claire mais tu as tres bien compris lol 
mais comment faire cela dans une routine de verification la personne donne exemple 21.5 et il dit mauvais et si la personne entre 22 il dit ok ;) ?

cs_Dobel · Answer

Salut
je suppose que tu travaille sur des String

je sais pas si ya plus propre

double temp = Double.parseDouble("2.01");
if ((temp-(int)temp)==0) {//si il est entier
    int p=(int) temp;
    //ect...
}

en tout cas, ya plus sale :

comme je suis super pointilleux : (lol)
si tu teste avec 2.0000000000000001
il te dit que c'est un entier car pour 1 double : 15chiffres significatifs

d'où (lol) la méthode du porc  :big) 
(je décline toute responsabilité quant aux dommages causés par la lecture de ce code de porc)
try {
    int n = Integer.parseInt("2");
    //etc
}
catch (Exception e) {
    //c'est pas un double
}

java permet de faire ce genre de truc mais je trouve que c'est quand même super crade ;-p

A+

DOBELIOU

kirua12 · Answer

perso j'utilise la méthode suivante pour vérifier si une String représente un entier :


String nombre="21.5";
int entier=0;
try{
entier=Integer.parseInt(nombre);
}catch(NumberFormatException e){
}


Si tu te prends l'exception c'est que ce n'est pas un entier.

Madvin · Answer

Salut,

les tests de primalités probabilistes ne sont pas tops car ils n'affirment pas à 100% qu'un nombre est premier.
Il existe de nombreux tests de primalités sûrs, tape ces mots clés dans un moteur de recherche et t'auras bon nombre de sites référencés.
En c++, le crible d'Erathostène (avec quelques petites optimisations simples) permet de tester la primalité d'entiers de 9 chiffres (< 2^32) pratiquement instantanément, et est donc largement suffisant. En Java, je sais pas j'ai jamais essayé.

Pour info, l'algorithme le plus efficace à ce jour pour tester la primalité des très grands nombres à été découvert il y a 2 ans par des chercheurs indiens, télécharge ce pdf si tu le veux (y a même la démonstration !!!):  
http://www.cse.iitk.ac.in/news/primality.pdf

Voilà, si ça peut t'aider.

@+

CHKDSK2K · Answer

yo yo, p'tit probleme là j'ai un Jtextarea que je converti en string, je converti en suite en double ... mais quand je passe du string en double il ajoute dernier le nombre .0 donc apres les transformations que je fait je le retransforme en STR et je verfie avec le 
try{
entier=Integer.parseInt(nombre);
}catch(NumberFormatException e){
}

et il me dit qu'il y a uen virgule je sais que c normal mais comment eviter que quand je passe du string en double il ajoute ''.0'' 

?

DOS

cs_Dobel · Answer

try{ entier=Integer.parseInt(nombre); }catch(NumberFormatException e){ } ->c'est vraiment crade (c'est ridicule de mobiliser des exceptions pour verifier si un nombre est entier) double temp = Double.parseDouble("2.01"); if ((temp-(int)temp)==0) {//si il est entier int p=(int) temp; //ect... } ca devrait mieux marcher avec :-) pour Madvin : je suis pas vraiment d'accord ;-p pas du tout en fait pour commencer, avec Rabin Miller, pour 50 itterations de l'algo, t'obtiens une proba d'erreur < 10^(-30) (faut vraiment avoir la poisse là pour que ca foire) et au niveau de la vitesse, pour des grands nombres, c'est vraiment dur de faire mieux (même celui présenté sur le pdf, qui est vraiment exceptionnel pour un algo deterministe, est bien plus lent) Rabin Miller a une complexité en O(t log(n)) où t est le nombre d'itérations et l'autre algo est en O(log(n)^12) d'apès le pdf ya pas photo là (même pour pitits nombres) :-p quant au crible d'erathostène : j'ai fait un chtit teste de vitesse (juste pour le fun ;-p) j'ai testé tout les nombres de 2 à 2^15=32768 (c'est à dire des petits nombres) 50 itérations sur Rabin Miller et un crible récupéré sur http://awr.free.fr/download/download.html qui a l'air correctement programmé (Athlon 1.4) 511 ms pour Mrs Rabin et Miller 10745 ms pour l'ancêtre autre essai : temps mis pour tester 4194319 (premier nombre premier après 2^22) : <10 ms pour Rabin Miller 771 ms pour Erathostène pour tester 268435459 (premier nombre premier après 2^28) : <10ms pour Rabin Miller java.lang.OutOfMemoryError pour Erathostène (c'est inévitable à cause de sa conception) :clown) :clown) -> Erathostène est inutilisable ya pas photo non plus (il doît quant même exister des algos deterministes simples un peu plus performants) Rabin Miller avec 50 itérations n'est absolument pas un luxe c'est idiot de passer à côté A+ DOBELIOU

cs_Dobel · Answer

Je sais c'est long à lire mais ca m'avais énervé
 :big)  :big) 

désolé ;-p

A+
DOBELIOU

kirua12 · Answer

Je suis pas vraiment d'accord avec toi sur le fait d'utiliser les exceptions pour tester si un nombre est entier soit crade. Je trouve au contraire que c'est très propre. Ca fait parti du modèle objet donc pourquoi s'en priver. Cela évite justement de faire toute une série de if pour tester si les données sont correctes.
Quand on veut accéder à un fichier qui n'existe pas on va se prendre une FileNotFoundException. C'est plus propre de que de tester si il existe sachant que ce n'est pas la seule opération que l'on va faire. On va donc entourer le code d'un ou plusieurs try catch sans se préoccuper de faire un certain nombre de tests.
Pour les nombres c'est pareil. On convertit le nombre et on fait le reste des opérations. Si la conversion échoue on se prend l'exception et c'est tout.
La remontée des erreurs par exception permet une gestion plus fine de ces erreurs. Ce n'est pas forcément là où on a détecté l'erreur qu'on peut la traiter (correction potentielle ou affichage d'un message). Sans les exceptions je vois mal comment faire ça.

OK ,c'est long aussi  :)  et on dévie énormément du sujet mais bon je trouve cette discussion intéressante.
Désolé aussi  :)

Madvin · Answer

Salut,

Dobel, désolé de t'avoir énervé, mais sache que pour un informaticien comme moi, l'un des points les plus importants est que son programme soit juste.
Oui, je sais que le test de Rabin-Miller marche bien dans la grande majorité des cas, mais dès qu'il y a, ne serait-ce qu'une infime possibilité que cela ne marche pas, ce n'est pas une solution acceptable, car le programme n'est pas du tout sûr.
Dit ça à un mathématicien et alors là, il s'arrache les cheveux.
Je sais pas si tu sais, mais il y a des récompenses de plusieurs milliers de dollars prévues pour ceux qui trouvent les plus grands nombres premiers à ce jour (de plusieurs millions de chiffres) (voir le site du gimp), et il est totalement exclus d'utiliser un algorithme probabiliste, même si pour les très grands nombres, les chances de tomber sur un mauvais cas sont pratiquement nulles. Il suffit qu'un algorithme ait 1 chance sur des millards de millards de millards de millards de millards...... de se tromper, pour qu'il ne soit pas acceptable pour pouvoir récupérer les gains de la récompense.
C'est la même chose pour un programme informatique, c'est inacceptable.

En ce qui concerne l'algorithme des chercheurs indiens, oui je sais qu'il est horrible, mais c'est le meilleur algorithme au niveau complexité. (C'est un algorithme déterministe de complexité polynomiale) Ce n'est pas forcément le meilleur pour des nombres relativement petits (plusieurs dizaines de chiffres), mais par contre, pour des nombres quelconques de plusieurs millions, ou plusieurs milliards de chiffres, il est pour l'instant imbattable.

Donc si un programme a besoin de tester la primalité de nombres d'une dizaine de chiffres, il existe des algorithmes sûrs, efficaces, et donc suffisants. Pas la peine d'utiliser un algo probabiliste qui rendrait le programme pas sûr, même si celui-ci est un peu plus rapide.

J'espère que tu vas pas à nouveau t'énerver, mais imagine que tu écrives un programme qui à besoin de tester à un moment ou un autre, la primalité de certains nombres, que tu utilises pour cela un algo probabiliste, ton programme n'est donc pas sûr à 100%, crois-tu vraiment que des entreprises voudront t'acheter un tel programme ? Surtout si c'est pour être utilisé dans les transports (trains, avions,....) ou l'aéronautique. Sache que des fusées de la Nasa ont déjà explosés à cause d'un programme informatique qui contenait un infime bug. Une toute petite erreur, et c'est la cata !!!!

Bon c'est vrai qu'on en est pas là, mais bon.... C'est pour te démontrer l'importance de la chose. :big) 

@+

cs_Dobel · Answer

Bonsoir tlm

argh, 2 discutions en même temps !!  :big) 

à propos des try catch ;-p
c'est sûr que ca peut-être pratique
même si dans certains cas, c'est plutôt de la paresse pour pas traiter tous les cas!
mais pour tester si un nombre est entier, je trouve que c'est un peu comme chasser le colibri au RPG (lol, ca doît être fun!)
c'est pas la finesse même quoi (duke3d-like)

globalement, je suis pour un minimum d'exceptions
car c'est bcp plus rapide de tester avec un if plutôt que de creer des exceptions, de les récupérer etc...
c'est juste que c'est bcp plus chiant à écrite  ;) 

hop, sujet suivant !! ;-)

d'abord merci pour ta réponse et merci de m'avoir fait connaître l'algo des Indiens (il est pas horrible du tout, il est même très bô!)
j'avais été quand même un peu pessimiste : il semble être au pire en O(log(n)^6) voir peut-être en O(log(n)^3) ;-p
(je m'étais énervé un peu facilement car je pensait à un TD de S.I. lol)
toujours pour les algos probabilistes, 
j'ai pas (encore?) un point de vu d'informaticien ou de matheux (je suis entre les 2, en prépas...)
les matheux recherchent les grand nombres premiers sans doute plus pour la beauté du truc (une secte?) et il leur faut des algos sûrs
mais l'utilisation principale reste (malheureusement!) la cryptographie qui demande de la vitesse et de l'efficacité
il faut remarquer que le risque d'erreur de l'algo rejoint le risque d'erreur dû au hardware!
remarque : "un peu plus rapide" -> BEAUCOUP plus rapide !!
(point de vu plus pessimiste, les principaux interressés par les grands nombres premiers restent les militaires pour la cryptographie, et je m'en fous qu'ils aient une certaine proba d'erreur  :big) )

(PS : j'espère ne pas paraitre trop enervé car j'ai tjrs pas fini ce TD de SI ;-p)

A+
DOBELIOU

Madvin · Answer

Salut,

voici une petite implémentation d'un test de primalité SÛR pour les integer utilisant une variante du crible d'érathostène comme je l'expliquais précédemment.
Le résultat est donné pratiquement instantanément sur un Pentium 4 1,2Ghz avec java 1.4.2 pour n'importe quel integer (ça ne dépasse jamais les 10ms).

public boolean estPremier(int n)
{
long timer = System.currentTimeMillis();

//Cas où le nombre à tester est négatif.
if (n<0)
{
System.out.println("Un test de primalité s'effectue sur un entier positif");
return false;
}

//Cas où le nombre à tester est 0 ou 1.
if (n<2)
{
System.out.println("Résultat trouvé en " + (System.currentTimeMillis() - timer) + " ms");
System.out.println(n + " n'est pas premier");
return false;
}

//Cas où le nombre à tester est 2.
if (n==2)
{
System.out.println("Résultat trouvé en " + (System.currentTimeMillis() - timer) + " ms");
System.out.println("2 est premier");
return false;
}

//Teste si le nombre est pair.
if (n%2 == 0)
{
System.out.println("Résultat trouvé en " + (System.currentTimeMillis() - timer) + " ms");
System.out.println(n + " est composé car divisible par 2");
return false;
}

//Calcul de l'entier successeur à la valeur entière de la racine carrée du nombre à tester.
int racn = new Double(Math.floor(Math.sqrt(n)) + 1).intValue();

//Cherche si le nombre à tester est divisible par un entier impair et inférieur à racn.
for (int i = 3; i<racn; i+= 2)
if (n%i == 0)
{
System.out.println("Résultat trouvé en " + (System.currentTimeMillis() - timer) + " ms");
System.out.println(n + " est composé car divisible par " + i);
return false;
}

//Sinon le nombre à tester est premier.
System.out.println("Résultat trouvé en " + (System.currentTimeMillis() - timer) + " ms");
System.out.println(n + " est premier");
return true;
}

Et voilou.  ;) 

@++

Madvin · Answer

PETITE ERREUR DANS LE CODE PRECEDENT :

Dans le cas où le nombre à tester est 2, faire return true !!! (et non return false comme indiqué dans le code).

Désolé.  :blush)

cs_Dobel · Answer

Oui, mais ce n'est pas ce que j'appelle le crible d'Eratosthène (et donc, ce n'est pas ce que j'avais utilisé dans les tests).
Pour rappel, le crible d'Eratosthène (je sais pas combien il y a de h dans le nom, ni où ;p) permet de tester tous les nombres <= à l'entier donné. Mais pour cela, il manipule des tableaux de longueur n...
Il est donc évidemment incomparable avec n'importe quel autre algo... 

Ce que tu fais (tester si le nombre n'a pas de diviseurs, en s'arretant là où c'est suffisant, soit ce qu'il y a de plus simple) est suffisant pour des Integer, et pe plus rapide que Rabin Miller (pas de tests, désolé, j'ai la flemme). Reste à voir ce que tu appelles un grand nombre  :big) 
Si la classe BigInteger propose une méthode de test porbabiliste, ce n'est pe pas pour rien ^^

sur ce, je vais faire une petite sièste  :sleepy) 

Dobel
[Une fois rien, c'est rien; deux fois rien, ce n'est pas beaucoup, mais pour trois fois rien, on peut déjà s'acheter quelque chose, et pour pas cher]

Madvin · Answer

Ouaih tu as raison, j'avais bien indiqué que c'était une variante, mais ce n'est pas vraiment un crible, erreur de ma part je le reconnais. Mais c'est un algo tout simple à implémenter qui permet de tester la primalité de nombre de 10 chiffres (Integer)instantanément. Par contre il y a forcément une limite acceptable de cet algo en fonction de la taille des entiers à tester, que je ne connais pas, mais le problème c'est d'avoir une implémentation de la fonction racine carrée sur les BigInteger. On peut l'implémenter soit même bien sûr mais bizarrement cette méthode n'a pas l'air d'être fournie avec la librairie.

++

Nombre Premier

23 réponses

Votre réponse

Discussions similaires