Facteur premier de 300 000 000 000?

https://stackoverflow.com/questions/439814

22-07-2019
|

Question

Je dois connaître les facteurs premiers de plus de 300 milliards. J'ai une fonction qui en ajoute à la liste ... très lentement! Il fonctionne depuis environ une heure maintenant et je pense qu’il a encore une bonne distance à parcourir. Est-ce que je le fais complètement mal ou est-ce prévu?

Éditer: Je cherche le plus grand facteur premier du nombre 600851475143.

Modifier: Résultat:

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

La solution

Vous souvenez-vous de diviser le nombre que vous factorisez par chaque facteur au fur et à mesure que vous les trouvez?

Disons, par exemple, que vous trouvez que 2 est un facteur. Vous pouvez ajouter cela à votre liste de facteurs, mais vous divisez ensuite le nombre que vous essayez de factoriser par cette valeur.

Maintenant, vous ne recherchez que les facteurs de 150 milliards. À chaque fois, vous devriez commencer par le facteur que vous venez de trouver. Donc, si 2 était un facteur, testez à nouveau 2. Si le facteur suivant que vous trouvez est 3, il est inutile de tester à nouveau sur 2.

Et ainsi de suite ...

Autres conseils

Il est difficile de trouver des facteurs premiers en utilisant la force brute, qui ressemble à la technique que vous utilisez.

Voici quelques astuces pour accélérer quelque peu:

Début bas, pas haut
Ne testez pas chaque facteur potentiel pour savoir s'il est premier - testez simplement des nombres premiers probables (les nombres impairs se terminant par 1,3,7 ou 9)
Ne vous fatiguez pas à tester les nombres pairs (tous divisibles par 2), ou les cotes se terminant par 5 (tous divisibles par 5). Bien sûr, ne sautez pas réellement les 2 et 5 !!
Lorsque vous trouvez un facteur premier, veillez à le diviser - ne continuez pas à utiliser votre grand nombre initial. Voir mon exemple ci-dessous.
Si vous trouvez un facteur, assurez-vous de le tester à nouveau pour voir s'il y figure plusieurs fois. Votre numéro pourrait être 2x2x3x7x7x7x31 ou quelque chose comme ça.
Arrêtez-vous lorsque vous atteignez > = sqrt (grand nombre restant)

Edit: un exemple simple: Vous trouvez les facteurs de 275.

Testez 275 pour la divisibilité par 2. 275/2 = int (275/2)? Non. En échec.
Testez 275 pour la divisibilité par 3. Échec.
Sautez 4!
Testez 275 pour la divisibilité par 5. OUI! 275/5 = 55. Votre nouveau numéro de test est donc 55.
Testez 55 la divisibilité par 5. OUI! 55/5 = 11. Votre nouveau numéro de test est donc 11.
MAIS 5 > sqrt (11), donc 11 est premier, et vous pouvez vous arrêter!

Donc 275 = 5 * 5 * 11

Plus de sens?

Factoriser de grands nombres est un problème difficile. Si difficile, en fait, que nous comptons sur lui pour sécuriser RSA Mais jetez un coup d’œil à la page wikipedia pour des liens vers des algorithmes pouvant vous aider. Mais pour un nombre aussi petit, cela ne devrait vraiment pas prendre autant de temps, à moins que vous ne recommenciez à travailler sans cesse et que vous n'ayez pas à vous rendre quelque part.

Pour la solution brute-force, rappelez-vous que vous pouvez effectuer quelques mini-optimisations:

Vérifiez 2 spécialement, puis ne vérifiez que les nombres impairs.
Vous devez uniquement vérifier jusqu'à la racine carrée du nombre (si vous ne trouvez aucun facteur d'ici là, le nombre est premier).
Une fois que vous avez trouvé un facteur, n'utilisez pas le nombre d'origine pour trouver le prochain facteur, divisez-le par le facteur trouvé et recherchez le nouveau nombre plus petit.
Lorsque vous trouvez un facteur, divisez-le autant de fois que vous le pouvez. Après cela, vous n’avez plus jamais besoin de vérifier ce nombre, ni aucun nombre inférieur.
Si vous effectuez toutes les opérations ci-dessus, chaque nouveau facteur trouvé sera primordial, car tous les facteurs plus petits ont déjà été supprimés.

Voici une solution XSLT!

Cette transformation XSLT prend 0,109 seconde .

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

Cette transformation produit le résultat correct (le facteur premier maximal de 600851475143) en seulement 0,109 seconde. :

6857

La transformation utilise le f: sqrt () et f: isPrime () défini dans FXSL 2.0 - une bibliothèque pour la programmation fonctionnelle en XSLT . Le FXSL est lui-même entièrement écrit en XSLT .

f: isPrime () utilise Le petit théorème de Fermat afin qu'il soit efficace pour déterminer la primalité.

Une dernière chose que personne n’a mentionnée, peut-être parce que cela semble évident. Chaque fois que vous trouvez un facteur et que vous le divisez, continuez d'essayer le facteur jusqu'à ce qu'il échoue.

64 a un seul facteur premier, 2. Vous le découvrirez assez trivialement si vous continuez à diviser le 2 jusqu'à ce que vous n'en puissiez plus.

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

Vous faites quelque chose de mal si cela prend une heure. Vous pourriez même avoir une boucle infinie quelque part - assurez-vous de ne pas utiliser d'ints 32 bits.

Pour comprendre pourquoi la racine carrée est importante, considérez que chaque facteur de n en dessous de la racine carrée de n correspond à un facteur au-dessus . Pour voir cela, considérons que si x est un facteur de n, alors x / n = m, ce qui signifie que x / m = n, donc m est également un facteur.

Je ne m'attendrais pas à ce que cela prenne très longtemps - ce n'est pas un nombre particulièrement élevé.

Pouvez-vous nous donner un exemple de numéro qui pose des problèmes de code?

Voici un site sur lequel vous pouvez obtenir des réponses: Factoris - Service de factorisation en ligne . Il peut faire de très grands nombres, mais il peut aussi factoriser des expressions algébriques.

Les algorithmes les plus rapides sont des algorithmes tamis et sont basés sur des zones obscures de mathématiques discrètes (au moins sur ma tête), compliquées à mettre en œuvre et à tester.

L’algorithme de factorisation le plus simple est probablement (comme d’autres l’ont déjà dit) le tamis d’Ératosthène. Ce qu'il faut retenir avant de l'utiliser pour factoriser un nombre N :

idée générale: vous vérifiez une suite croissante de facteurs entiers possibles x pour voir s'ils divisent également votre numéro de candidat N (en C / Java / Javascript) si N% x == 0 ), auquel cas N n'est pas premier.
il vous suffit de monter jusqu'à sqrt (N) , mais ne calculez pas réellement sqrt (N) : en boucle tant que votre facteur de test x passe le tester x * x < N
si vous avez assez de mémoire pour sauvegarder un ensemble de nombres premiers précédents, utilisez uniquement ceux-ci comme facteurs de test (et ne les sauvegardez pas si le nombre premier P échoue au test P * P> 0_max depuis vous ne les utiliserez plus jamais
Même si vous n'enregistrez pas les nombres premiers précédents, pour les facteurs possibles x , cochez simplement 2 et tous les nombres impairs. Oui, cela prendra plus de temps, mais pas beaucoup plus longtemps pour les nombres de taille raisonnable. La fonction de décompte des nombres premiers et ses approximations peuvent vous indiquer quelle fraction de nombres est composée de nombres premiers; cette fraction diminue très très lentement. Même pour 2 ⁶⁴ = environ 1,8 x 10 ¹⁹, environ un chiffre sur 43 correspond au nombre premier (= un nombre impair sur 21, soit le nombre premier). Pour les facteurs de nombres inférieurs à 2 ⁶⁴, ces facteurs x sont inférieurs à 2 ³² où environ un nombre sur 20 est premier = un sur 10 chiffres impairs est premier. Vous devrez donc tester 10 fois plus de nombres, mais la boucle devrait être un peu plus rapide et vous n'avez pas à vous soucier de stocker tous ces nombres premiers.

Il existe également des algorithmes de tamis plus anciens et plus simples, un peu plus complexes, mais néanmoins assez compréhensibles. Voir de Dixon , Shanks ' et Fermat's algorithmes de factorisation. J'ai lu un article sur l'un de ces objets une fois, je ne me souviens plus lequel, mais ils sont tous assez simples et utilisent les propriétés algébriques des différences de carrés.

Si vous testez simplement si un nombre N est primordial et que vous ne vous souciez pas des facteurs eux-mêmes, utilisez un test de primalité probabiliste . Miller-Rabin est, à mon sens, le plus standard.

J'ai passé un peu de temps là-dessus, car cela m'avait absorbé. Je ne vais pas coller le code ici pour l'instant. Consultez plutôt ce facteur.py gist si vous êtes curieux.

Remarquez, je ne connaissais rien au factoring (toujours pas) avant de lire cette question. Il s’agit simplement d’une implémentation Python de la réponse à BradC ci-dessus.

Sur mon MacBook, il faut 0,002 seconde pour factoriser le nombre mentionné dans la question (600851475143).

Il doit évidemment y avoir beaucoup plus de moyens beaucoup plus rapides de le faire. Mon programme prend 19 secondes pour calculer les facteurs de 6008514751431331. Mais le Factoris " crache la réponse en un rien de temps.

Le numéro spécifique est 300425737571? Il tient compte de 131 * 151 * 673 * 22567. Je ne vois pas ce que tout le monde veut faire.

Voici un peu de bonté Haskell pour vous les gars:)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

Il a fallu environ 0,5 seconde pour les trouver, alors j’appellerais cela un succès.

Vous pouvez utiliser le tamis d'Eratosthenes pour trouver les nombres premiers et savoir si votre numéro est divisible par ceux que vous trouvez.

Il vous suffit de vérifier le reste, mod (n), où n est un nombre premier < = sqrt (N), où N est le nombre que vous essayez de factoriser. Cela ne devrait vraiment pas prendre plus d’une heure, même sur un ordinateur très lent ou une TI-85.

Votre algorithme doit être FUBAR. Cela ne prend que 0,1 s environ sur mon netbook 1,6 GHz en Python. Python n'est pas connu pour sa vitesse fulgurante. Cependant, il a des entiers de précision arbitraire ...

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

(Ce code semble fonctionner au mépris du fait que je ne connais pas suffisamment la théorie des nombres pour remplir un dé à coudre.)

Juste pour développer / améliorer légèrement le " testez uniquement les nombres impairs qui ne se terminent pas par 5 " suggestions ...

Tous les nombres premiers supérieurs à 3 sont soit un de plus, soit un de moins d'un multiple de 6 (6x + 1 ou 6x - 1 pour les valeurs entières de x).

Cela ne devrait pas prendre si longtemps, même avec une force brute relativement naïve. Pour ce nombre spécifique, je peux le prendre en compte en une seconde environ.

Vous dites que vous ne voulez pas de solutions (?), mais voici votre "subtile". allusion. Les seuls facteurs premiers du nombre sont les trois premiers nombres les plus bas.

Les nombres semi-premiers de cette taille sont utilisés pour le cryptage. Je suis donc curieux de savoir à quoi cela sert de vouloir les utiliser.

Cela dit, il n’existe actuellement pas de bonne méthode pour déterminer la factorisation initiale de grands nombres dans un laps de temps relativement court.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow