[HELP] programme en c++ "multiplications"

[nikitouzz]

Bonjour, je voudrais calculer un nombre premier avec plus d' 1millions de chiffres (un pari avec un pote....)....

pour ça quoi de plus plus simple que la formule P(n)=n!+1 X)

Mais pour faire un nombre avec plus d' 1 millions de chiffre je dois faire des GROOOSSSEEESS multiplications !

Donc soit il existe déjà un programme pour ceci sur Windows

soit je dois le programmer en c++ !

si je dois le programmer :
-quel technique le conseiller vous pour programmer la multiplications de deux chaîne de caractère en c++ ? genre "12"*"50"="600 ?
-on peux tester la longueur d'une chaîne d'1 millions au moins de caractère ?
-que me conseiller vous ?...4


merci d'avance

[Excale]

Donc soit il existe déjà un programme pour ceci sur Windows

Si tu optes pour la solution toute faite, regarde parmi (sans ordre):
-MPIR
-BigInt
-GMP

[nikitouzz]

J'ai regarder GMP mais incapable de l'installer !

[Bisam]

Non, programme-le !
C'est un super bon exercice...

[Lionel Debroux]

Avec GMP / MPIR, il est en effet trivial de gérer des nombres qui font des millions de chiffres.
Programmer soi-même ce genre d'algorithmes prend plus de temps, naturellement ^^

Sauf rare exception (certaines classes précises de nombres tels que les nombres de Mersenne 2^p-1 et quelques autres), il est impossible de déterminer à coup sûr la primalité d'un nombre d'un million de chiffres. Seuls les algorithmes probabilistes comme Rabin-Miller donnent une réponse "probablement premier".

[nikitouzz]

mais on peux generer facilement des nombre premier de N chiffre N→oo avec n!1 entre autres ! comment utiliser GMP ? ou MPIR ?

[Excale]

comment utiliser GMP ? ou MPIR ?

Il faut réussir à compiler la lib

[Bisam]

Oui, ou encore, programmer soi-même...
Ce n'est pas la mer à boire, franchement (du moins, si l'on se contente de l'approche "triviale")
Il faut juste gérer des listes d'entiers de taille fixe (par exemple limités à 10^18, si tes entiers sont codés sur 64 bits) et programmer les 4 opérations avec gestion des retenues, etc...

Je tiens quand même à te signaler que ta fameuse formule P(n)=n!+1 ne fournit pas forcément un nombre premier !! Elle fournit un nombre dont le plus petit facteur premier est supérieur strictement à n, ce qui est complètement différent, car il faut ensuite déterminer ce facteur !

Par exemple : P(4)=25 dont le plus petit facteur premier est 5 ou encore P(13)=6227020801, dont le plus petit facteur premier est 83...
En fait, les cas où P(n) est premier sont même rares. Seuls n=2, 3, 11, 27 donnent des premiers pour n<=30.

[nikitouzz]

Bisam mes nombre doivent avoir au moins 1 000 000 de chiffre... donc en 64 bit ça va etre compliqué !

Bisam tu aurais pas une formule pour donner un nombre premier random ?


EDIT : n*n + n + 41 marcherais.... Boisam tu saurais comment prouver que cette formule donne un nnombre premier ! ?

RE-EDIT : enfaite ca marche pour qu'un certain n max..... après y'a 2^p-1 qui fonctionne tout le temps ! mais bon faut encore trouver un p premier mais je peux faire des iterations....

[Lionel Debroux]

Pour la simple recherche de tous les nombres dérivés d'une certaine formule, possédant une certaine propriété, sur une certaine plage, je sais que certains, sur MersenneForum, aiment beaucoup PARI/GP.

Bisam tu saurais comment prouver que cette formule donne un nombre premier ! ?

Aucune formule simple ne produit de nombre premier aléatoire pour des valeurs arbitraires de n. Rien que trouver une formule A(n) qui produit des nombres premiers quel que soit n entre 1 et 50 est très difficile, alors une formule valable pour n entre 1 et 100...

après y'a 2^p-1 qui fonctionne tout le temps ! mais bon faut encore trouver un p premier mais je peux faire des iterations....

Les nombres premiers de Mersenne sont très rares. On n'en connaît que 48, le 48ème étant 2^57885161-1, et il n'y a eu de vérification que jusqu'au 43ème (depuis hier). Voir http://mersenne.org/ .
Ce n'est pas difficile de trouver un petit nombre p premier, la division entière triviale (TF) est acceptablement rapide jusqu'à quelques milliers, voire quelques dizaines de milliers. C'est avec un bête TF (même pas de crible !) que j'ai fait ceux des problèmes du projet Euler liés aux nombres premiers auxquels j'ai répondu. Ca commencerait à être un peu lent pour répondre au problème 41, par exemple ("Pandigital prime").