[Java] Nombres Premiers

12 octobre 2006 à 0:03:04

Bonsoir à tous

J'aimerais savoir s'il n'existerais pas un autre moyen pour déterminer les nombres premiers jusqu'à n.

import algo.outils.*;

public class Nombres_Premiers
{
public static void main ( String [] args )
{
Clavier c = new Clavier();
int n = c.lireInt(" Choisissez l'entier n jusqu'auquel vous souhaitez afficher les nombres premiers. n = ");
int j ;
for (j=0;j<n;j++)
{
affichage(j);
}
}

public static void affichage ( int n )
{
int i , milieu ;
i = 2 ;
milieu = ( n / 2 ) ;
while ( ( n % i ) != 0 ) //tant que i n'est pas diviseur de n
{
if ( i == milieu )
{
break ;
}
else
{
i++ ;
}
}
if ( i == milieu ) //si l'on a parcouru toute la boucle while
{
if ( n % milieu == 0 )
{
System.out.println ( n + " n'est pas premier. Il est multiple de " + milieu ) ;
}
else
{
System.out.println ( n + " est premier. " ) ;
}
}
else //si l'on est sorti avant la fin du while, c'est que i est diviseur de n
{
System.out.println ( n + " n'est pas premier. Il est multiple de " + i ) ;
}
}
}

Only limits are ours...

kokotchY

12 octobre 2006 à 9:30:58

Ton code n'est vraiment pas beau :x
De plus, il y a plein d'erreurs !

Citation

2 n'est pas premier. Il est multiple de 2

Justement, 2 est premier car il n'est divisible que par 1 et 2 !

Regarde mon code (qui est un peu plus petit et logiquement un rien plus rapide) :

public static void affichage2 (int n) {
int i = 2;
int mul = 0;
boolean prems = true;
while ((i*i < n) && (prems)) {
if (n % i == 0) {
prems = false;
mul = i;
}
i++;
}
if (prems)
System.out.println(n + " est premier.");
else
System.out.println(n + " n'est pas premier. Il est multiple de "+mul);
}

Sinon, si tu veux une autre méthode, faut avoir quelques connaissances en math

SuperMat

12 octobre 2006 à 10:21:30

Oui, ce code est beaucoup mieux. Sinon pour les grands nombres on utilise souvent le test de Miller-Rabbin (probabiliste). Et pour trouver rapidements des grands nombres premiers on utilise le test de Lucas-Lehmer qui détecte si un Mersenne est premier ou non.

Mais si on veut tous les entiers premiers jusque N, une des méthodes les plus rapides restent le crible d'Ératosthène. Je parle bien de rapidité, pas de mémoire utilisée...

Le deuxième code peut être optimisé en testant la divisibilité par 2 au début, puis d'incrémenter i par pas de 2 : 3,5,7...

On a toujours la même complexité asymptotique mais l'exécution est deux fois plus rapide

Asphator

12 octobre 2006 à 23:36:33

Citation : kokotchY

Sinon, si tu veux une autre méthode, faut avoir quelques connaissances en math

Je veux bien un aperçu de cette 2e méthode stp

Sinon, pourquoi i*i dans le while?

Only limits are ours...

Dentuk

13 octobre 2006 à 19:06:24

Citation : Asphator

Sinon, pourquoi i*i dans le while?

Une fois que tu as vérifié que tous les nombres inférieurs ou égaux à la racine de i ne sont pas des diviseurs de i, pas la peine d'aller plus loin, i est premier.
(i * i = i²)

PS : Je mettrais plutot <= n moi