la liste n'est pas fermée à la fin du calcul

Question

Pour m'entraîner, j'ai écrit un programme Haskell pour trouver les facteurs premiers.

Le code est le suivant :

getfactors :: Int -> [Int]
getfactors n = [x | x<-[1..n], n `mod` x == 0]

prime :: Int -> Bool
prime n | getfactors n == [1,n] = True
        | otherwise              = False

primefactors :: Int -> [Int]
primefactors n = [x | x <- getfactors n, prime x == True]

Tout fonctionne bien pour les petits nombres, mais lorsque j'entre de grands nombres, le calcul s'arrête au plus grand facteur premier et la liste attendue ne se ferme pas. Par exemple :

>primefactors 1263
[3,421]
>primefactors 1387781234
[2,7,2161,6553

Une explication est très appréciée.

Answer 1

Impossible à reproduire :

> :set +s
> primefactors 1387781234
[2,7,2161,6553]
(368.04 secs, 288,660,869,072 bytes)

Votre algorithme est juste très lent. Il y a de nombreuses façons de l'améliorer :

• Vous vérifiez la primalité par la division d'essai de tous les nombres plus petits que le candidat. Vous pouvez améliorer (sans changer l'algorithme) en vérifiant seulement jusqu'à la racine carrée du candidat.
• Outre la division d'essai, il existe un large éventail d'autres algorithmes de vérification de la primalité, allant de "simple mais lent" à "compliqué à souhait mais extrêmement rapide". D'autres sources Internet vous fourniront de nombreux détails.
• Si vous voulez factoriser de nombreux nombres, il peut être bénéfique de mémoriser vos contrôles de primalité entre les appels -- par exemple en stockant une liste de nombres premiers et en itérant sur ceux-ci au lieu d'itérer sur tous les nombres. Puisque c'est le seul consommateur de votre contrôle de primalité, vous pouvez envisager de créer cette liste directement plutôt que d'implémenter d'abord un algorithme de contrôle de primalité ; encore une fois, il existe une large gamme d'algorithmes pour cela, allant du simple au rapide.
• Une fois que vous avez trouvé un facteur, vous pouvez diviser le nombre que vous mettez en facteur par celui-ci pour obtenir un nombre plus petit et plus rapide avec lequel calculer les facteurs restants.

Il y a probablement d'autres possibilités d'accélérer les choses, et beaucoup de travaux antérieurs à lire en ligne. Bonne lecture !