Comment trouver un nombre premier?
dans Arithmétique
Bonjour,
En multipliant un nombre premier par deux
puis en lui ajoutant ou en lui soustrayant un nombre premier autre que 2
on tombe plus facilement sur un nombre premier que si on choisit un nombre au hasard,
Il y a aussi les multiples de 6 +/- un nombre premier
Est-ce que vous connaissez d'autres astuces pour tomber encore plus facilement sur un nombre premier?
Merci ^^
En multipliant un nombre premier par deux
puis en lui ajoutant ou en lui soustrayant un nombre premier autre que 2
on tombe plus facilement sur un nombre premier que si on choisit un nombre au hasard,
Il y a aussi les multiples de 6 +/- un nombre premier
Est-ce que vous connaissez d'autres astuces pour tomber encore plus facilement sur un nombre premier?
Merci ^^
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Multiplier entre eux les nombres premiers consécutifs, en commençant par 2. La liste peut être aussi longue que l'on veut, que l'on peut. Ceci fait, ajouter 1.
et est-ce que du coup il existe autre chose qui ressemble à :
"Multiplier entre eux les nombres premiers consécutifs, en commençant par 3. La liste peut être aussi longue que l'on veut, que l'on peut. Ceci fait, ajouter (ou retrancher) 2."
?
C'est le théorème des nombres premiers : $\frac{\pi(N)}{N} \sim \frac{1}{\log N}$.
Maintenant si tu prends un nombre $n$ uniformément entre $1$ et $N$ mais uniquement parmi ceux qui sont premiers avec $m$ où $m! \le N$, alors (quand $\frac{N}{m!} \to \infty$) tu obtiens une probabilité qui tend vers $\displaystyle \frac{\pi(N)-\pi(m)}{\frac{\phi(m!)}{m!}N} \sim \frac{\frac{N}{\log N}-\frac{m}{\log m}}{m! N\prod_{p \le m} (1-\frac{1}{p})}\sim \frac{\frac{N}{\log N}-\frac{m}{\log m}}{ N\frac{e^{-\gamma}}{ \log m}}\ $ que $n$ soit premier.
Il faudrait préciser ta question.
Tu veux trouver un nombre premier plus grand que N, un entier donné à l'avance?
Tu veux un algorithme ou un moyen effectif de le faire?
Dans GP Pari il y a une fonction qui s'appelle nextprime() et qui trouve des pseudo nombres premiers (ils peuvent être réellement premiers mais il y a un risque faible qu'ils ne le soient pas. Il y a aussi une fonction isprime() qui renvoie 1 si le nombre est vraiment un nombre premier. On peut produire ainsi un nombre premier de plus de 400 chiffres.
C'est la description de la preuve classique par Euclide que les nombres premiers sont en nombre infini. Il faut bien sûr veiller à commencer par 2 et à ce qu'il n'y ait pas de trous. Pour cela il faut avoir déterminé les "petits" nombres premiers, d'où le "que l'on peut".
Je ne prétends pas que cela fournisse tous les nombres premiers.
Ai-je commis une erreur ?
Amicalement
Ton calcul garantit seulement que si le produit des n premiers nombres premiers auquel on ajoute un est un nombre premier alors ce nombre premier est au moins égal au (n+1) ème nombre premier.
PS:
Un diviseur premier de ce nombre est au moins égal au (n+1) ème nombre premier.
$N=\prod_{k=1}^{20}p_k+1$ est divisible par $1063$ et $p_{21}=73$
Encore une illusion qui s'effondre !