CHKDSK2K
Messages postés144Date d'inscriptionmardi 2 septembre 2003StatutMembreDernière intervention18 septembre 2007
-
28 mars 2004 à 21:44
Madvin
Messages postés123Date d'inscriptionmardi 5 août 2003StatutMembreDernière intervention26 août 2012
-
20 déc. 2004 à 16:34
Bonjour,
Je voudrais savoir comment on peut faire pour verifier qu'un nombre est premier facillement ?
Merci de votre aide
@+++
DOS
A voir également:
Algorithme nombre premier java
Afficher les n premiers nombres premiers java - Meilleures réponses
CHKDSK2K
Messages postés144Date d'inscriptionmardi 2 septembre 2003StatutMembreDernière intervention18 septembre 2007 29 mars 2004 à 17:35
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 ...
kirua12
Messages postés1155Date d'inscriptionsamedi 17 janvier 2004StatutMembreDernière intervention29 avril 20117 29 mars 2004 à 18:16
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
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 29 mars 2004 à 19:23
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
Vous n’avez pas trouvé la réponse que vous recherchez ?
cs_GodConan
Messages postés2113Date d'inscriptionsamedi 8 novembre 2003StatutContributeurDernière intervention 6 octobre 201212 29 mars 2004 à 19:30
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)
CHKDSK2K
Messages postés144Date d'inscriptionmardi 2 septembre 2003StatutMembreDernière intervention18 septembre 2007 29 mars 2004 à 21:22
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
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 30 mars 2004 à 13:31
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
CHKDSK2K
Messages postés144Date d'inscriptionmardi 2 septembre 2003StatutMembreDernière intervention18 septembre 2007 30 mars 2004 à 20:50
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
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 30 mars 2004 à 23:58
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
Madvin
Messages postés123Date d'inscriptionmardi 5 août 2003StatutMembreDernière intervention26 août 20123 31 mars 2004 à 15:01
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
CHKDSK2K
Messages postés144Date d'inscriptionmardi 2 septembre 2003StatutMembreDernière intervention18 septembre 2007 31 mars 2004 à 18:45
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''
(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é
kirua12
Messages postés1155Date d'inscriptionsamedi 17 janvier 2004StatutMembreDernière intervention29 avril 20117 1 avril 2004 à 09:38
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
Messages postés123Date d'inscriptionmardi 5 août 2003StatutMembreDernière intervention26 août 20123 1 avril 2004 à 14:23
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
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 1 avril 2004 à 22:33
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)
Madvin
Messages postés123Date d'inscriptionmardi 5 août 2003StatutMembreDernière intervention26 août 20123 20 déc. 2004 à 04:16
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;
}