1votos

Número con mayor cantidad de divisores en Haskell

por josejuan hace 6 años

Por "inducción".

Escribir una función que encuentre un número entre 1 y N que posea el mayor número de divisores posibles (en el menor tiempo posible).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import Data.Numbers.Primes (primes) 
import Data.List (sortBy) 
import System.Environment (getArgs) 
 
-- Obtiene los primeros primos cuyo producto no supera un número dado: 
primeCover :: Integral i => i -> [i] 
primeCover n = takeWhile (\p -> n >= product (takeWhile (<=p) primes)) primes 
 
-- Potencia máxima sin sobrepasar 
lowPower :: Integral i => i -> i -> i 
lowPower n p = floor (log (fromIntegral n) / log (fromIntegral p)) 
 
 
-- Calcula la forma de maximizar las potencias a partir de un conjunto de primos: 
coverPowers :: Integral i => i -> i -> [i] -> (i, [(i, i)]) 
 
coverPowers n maxq (p:[]) = if n < p then (1, []) else (maxq' + 1, [(maxq', p)]) 
  where maxq' = min maxq (lowPower n p) 
   
coverPowers n maxq (p:ps) = if n < p then (1, []) else last $ sortBy ((.fst).compare.fst) alternatives 
  where maxq' = min maxq (lowPower n p) 
        alternatives = [alternative x | x <- [1..maxq']] 
        alternative x = ((x + 1) * x', (x, p):ps') where (x', ps') = coverPowers (n `div` (p^x)) x ps 
 
-- Calcula el mayor número de divisores (en la forma en que hay mayor número de primos pequeños que grandes) 
maxCover :: Integral i => i -> (i, [(i, i)]) 
maxCover n = coverPowers n n $ primeCover n 
 
 
-- Igual, pero además muestra un número de los posibles 
maxCover' :: Integral i => i -> (i, [(i, i)], i) 
maxCover' n = (q, xs, product $ map (uncurry $ flip (^)) xs) where (q, xs) = maxCover n 
 
main = getArgs >>= print.maxCover'.read.head 
 
{-- 
 
En un Atom D510: 
 
solveet$ time -f "%E, %M" ./i1m2012 1000000000000000000000 
( 368640 
, [(7,2),(4,3),(2,5),(2,7),(1,11),(1,13),(1,17),(1,19),(1,23),(1,29),(1,31),(1,37),(1,41),(1,43)] 
, 791245405339403414400 
0:00.43, 2656 
 
 
solveet$ time -f "%E, %M" ./i1m2012 1000000000000000000000000000000 
( 13271040 
, [(9,2),(5,3),(3,5),(2,7),(2,11),(2,13),(1,17),(1,19),(1,23),(1,29),(1,31),(1,37),(1,41),(1,43),(1,47),(1,53),(1,59)] 
, 997755724485463775925981888000 
0:04.06, 3796 
 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.