Discussion :

[mcherkao88]

Bonjour,
Je me demande s'il y a moyen de générer le plus grand nombre premier plus petit qu'un certain BigInteger en java. Quelque chose genre nextProbablePrime() de la classe BigInteger mais à l'envers et merci.

[Invité]

Bonjour,
Un nombre premier n'est divisible que par un et par lui-même.
Donc, je ferais une boucle décroissante en partant de BigInteger, et je m'arrêterais au premier entier rencontré.

[Champialex]

Tu a la fonction probablePrime qui devrait t'interesser : http://download.oracle.com/javase/1....a.util.Random)
Cependant, on ne dispose pas d'algorithme rapide pour trouver la suite des nombres premiers, par contre, on sait facilement vérifier qu'un nombre est premier ou non, donc ce que tu peux faire c'est descendre les nombres jusqu'à en trouver un premier (le problème c'est que la concentration des nombres premiers diminue au fur et à mesure... )

[mcherkao88]

merci pour vos réponses.
Le problème c'est que je travaille avec des BigInteger. Ça risque d'alourdir trop mon programme.
Ce que j'aime faire c'est en quelque sorte la même chose que la fonction nextProbablePrime() mais juste à l'envers. Et si cette fonction marche vite, alors je pense qu'il y aura une solution plus rapide que le parcours brutal et merci encore.

[Invité(e)]

Bonjour,

Si tu ne cherches pas l'exact nombre premier précédent ton nombre, tu peux peut-être raisonner comme cela :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
BigInteger borne;
BigInteger prime;
BigInteger test = borne;
BigInteger step = 10;
 
do {
    test = test - step;
    step *= 2;
    prime = test.nextProbablePrime();
} while(prime > borne);

[mcherkao88]

En fait oui. J'ai besoin de l'exact nombre premier précédent mon nombre et merci.

[droggo]

Kai,

Alors une seule solution, éplucher en descendant ...

[Invité]

Je veux bien vous l'écrire en C, mais pas en Java.

[benDelphic]

crible d' Eratosthène !!!

[Invité(e)]

crible d' Eratosthène !!!

J'ai bien peur que le crible d'Eraosthène ne soit pas performant pour les grands nombres.

En fait oui. J'ai besoin de l'exact nombre premier précédent mon nombre et merci.

Une adaptation :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
BigInteger borne;
BigInteger prime;
BigInteger test = borne;
BigInteger step = 10;
 
// recherche d'un premier plus petit que borne
 
do {
    test = test - step;
    step *= 2;
    prime = test.nextProbablePrime();
} while(prime > borne);
 
// recherche du premier précédent borne (à partir du précédent trouvé)
test = prime;
 
while(test < borne) {
    prime = test;
    test = prime.nextProbablePrime();
}

NB : cette méthode n'est pas completement fiable dans la mesure où il y a le mot probable dans nextProbablePrime.

[Champialex]

Perso, je n'ai pas trouvé de fonction nextProbablePrime() dans la javadoc... Il y a bien probablePrime(), mais c'est tout (certes tu choisis la longueur de ton nombre)... Sinon, la probabilité que le nombre retourné ne soit pas premier est de 2^-100, on peut donc se dire que c'est plutôt fiable !

[Invité]

Voici un petit programme qui réalise ce calcul.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
long PremierInf(long N)
{
  long RacN = (long)sqrt((double)N);
  for (long i=N-1; i>1; i--)
  {
    bool estpremier=true;
    for (long j=2; j<RacN; j++)
    {
      if (i%j == 0) // i n'est pas premier
      {
        estpremier = false;
        break;
      }
    }
    if (estpremier) return i;
  }
  return 1;
}
 
int main()
{
  randomize();
  for (int i=0; i<10; i++)
  {
    long N=15 + random(MAXLONG-17);
    long prem=PremierInf(N);
    printf(" N=%d  prem=%d\n",N,prem);
  }
  system("Pause");
  return 0;
}

Pour 10 valeurs essayées, le calcul est sans approximation et immédiat.

[Champialex]

Le problème, c'est qu'un long en C, ca monte max jusqu'à 10^10, alors que le BigInteger de java peut facile faire du 10^50 (environ 10^20 fois plus long pour ton programme, ce qui est quand même non négligeable... ), ce qui prolonge nettement les calculs... D'où l'utilisation de fonctions probabilistes, donc tant qu'à faire des fonctions prédéfinies en java, même si pour le fun on peut recoder les algos...

[mcherkao88]

Bonjour
J'ai enfin essayé un truc qui a bien marché. Sur java, j'utilise nextProbablePrime(). Ce que j'ai fait c'est reculer de ma borne par 10, 20, 40, 80, 160, 320 ... jusqu''a ce que le nombre premier suivant soit inférieur à ma borne (merci "mabu", c'est ton idée). Jusque là, c'est pas forcé que ce nombre soit le plus grand (ainsi on rétréci le champ d'étude ). Alors je remonte encore par la même fonction prédite jusqu'à dépasser notre borne. Merci pour vous tous et si quelqu'un a une méthode plus efficace qu'elle soit la bienvenue.
Autre chose, j'ai besoin encore d'un algorithme pour calculer le PGCD(P(x), Q(x)) de deux polynômes. Y a Euclide mais je sais pas comment l'implémenter et merci encore.

[pseudocode]

J'arrive après la bataille. L'algo utilisé pour nextProbablePrime() consiste a tester successivement chaque nombre avec le test de primalité de Miller-Rabin, accesible par la méthode isProbablePrime().

On peut donc coder facilement un previousProbablePrime().

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
public static BigInteger previousProbablePrime(BigInteger n) {
	BigInteger previous = n.subtract(BigInteger.ONE);
	while(previous.signum()>0) {
		if (previous.isProbablePrime(100)) return previous;
		previous=previous.subtract(BigInteger.ONE);
	}
	throw new ArithmeticException("No more prime before " + n);
}

[mcherkao88]

Oui !! Ça marche très bien
merci beaucoup pseudocode et à tous ceux qui ont contribué en cette discution .