Création d'une liste infinie dans Haskell de nombres k-composites

Question

Un nombre k-composite est un nombre composé avec k facteurs à l'exclusion de 1 et lui-même. J'essaie d'écrire du code qui prendra un entier k et retournera une liste infinie de tous les k-composites. Donc, en utilisant prendre 5 $ kcomposite 2 retournera [6,8,10,14,15]. J'ai écrit deux fonctions pour accomplir cette tâche:

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

kcomposite :: Int -> [Int] 
kcomposite n = [x | x <- [1..], (length (factors n)) == (x-2)] 

Je n'ai pas du mal à la compilation, mais lorsque je tente de les exécuter, le ghci ne cesse de courir. Cela est logique en raison de la liste infinie, mais cela se produit même lorsque j'essaie seulement d'obtenir les premiers éléments de la liste, comme dans l'exemple ci-dessus. Je ne peux pas comprendre ce que je fais mal.

Answer 1

Un certain nombre de k-composite est un nombre composé de facteurs k excluant 1 et se

Depuis votre fonction factors renvoie tous les facteurs d'un nombre (y compris 1 et lui-même), ce nombre sera plus que le k fourni. Voilà pourquoi vous devez comparer avec k + 2 au lieu de k - 2

En outre, lorsque k est inférieur à 0 vous aurez toujours le programme en cours d'exécution ne jamais cesser, c'est la raison pour laquelle vous pourriez vouloir traiter ce cas limite.

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

kcomposite :: Int -> [Int] 
kcomposite k 
    | k < 0 = [] 
    | otherwise = [x | x <- [1..], length (factors x) == (k + 2)] 

Answer 2

Voici mon approche légèrement différente pour cette tâche qui est beaucoup plus efficace.

La clé est de stimuler pas vérifier tout le chemin jusqu'à la fin, mais seulement jusqu'à sa racine carrée. Je veux dire que si nous voulons trouver des composites de 100, nous n'avons pas besoin de contrôler tous les 100 nombres. Nous avons seulement besoin de contrôler jusqu'à sqrt 100 (comme [2..10]) pour voir (mod 100 x) == 0. Nous commençons à partir de 2 puisque vous ne voulez pas 1 et le nombre lui-même. Une fois que nous avons les chiffres satisfaisants 100 div x devrait nous donner l'autre. Donc, si 2 est un composite alors 100 div 2 (50) est un autre comme 4 rendements 25 et 5 rendements 20. Bien sûr, quand nous arrivons à 10, il nous en donnera 10 autres et nous n'évaluerons que l'un d'entre eux. Cool..!

Donc, c'est le code

kcomposites :: Int -> [Int] 
kcomposites k = 
    let factors n = concat [bool [x, n `div` x] [x] (x^2 == n) 
          | x <- [2..limit], n `mod` x == 0] 
      where limit = truncate . sqrt . realToFrac $ n 
    in foldr (\n rs -> bool rs (n:rs) (k == (length . factors $ n))) [] [2..] 

Voici les performances de ce code pour k = 19 pour les premiers 5 éléments;

*Main> take 5 . kcomposites $ 19 
[576,1600,2916,3136,7744] 
(0.43 secs, 174,826,272 bytes) 

et voici la performance de votre code pour k = 19 pour les 5 premiers éléments;

*Main> take 5 . kcomposite $ 19 
[576,1600,2916,3136,7744] 
(17.61 secs, 6,246,022,504 bytes) 

Note: Je ne conseillerais pas de vérifier k = 5 pour 5 éléments. Même ce code a pris comme 15 minutes pour arriver à [64,729,15625,117649,1771561] le code ci-dessus prendra probablement une quantité folle de temps (comme un jour ou plus peut-être).

Permet de les comparer avec take 3.

*Main> take 3 . kcomposites $ 5 
[64,729,15625] 
(1.14 secs, 472,228,880 bytes) 

*Main> take 3 . kcomposite $ 5 
[64,729,15625] 
(69.84 secs, 25,409,801,688 bytes)