Основные факторы в Haskell

Ответ 1

Простой подход для определения простых множителей n равен

• найдите первый делитель d в [2..n-1]
• если существует D: return d : primeFactors(div n d)
• иначе return n (так как n является простым)

Код:

prime_factors :: Int -> [Int]

prime_factors 1 = []
prime_factors n
  | factors == []  = [n]
  | otherwise = factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]

Это, очевидно, может использовать большую оптимизацию (поиск только от 2 до sqrt (N), кеширование простых чисел, найденных до сих пор, и вычисление деления только для этих и т.д.)

UPDATE

Немного измененная версия с использованием case (как предложено @user5402):

prime_factors n =
  case factors of
    [] -> [n]
    _  -> factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]

Ответ 2

До тех пор, пока дивиденд m 2,

• возьмем первый делитель n из простых чисел.
• повторить деление m на n в то время как делится.
• возьмите следующий делитель n из простых чисел и перейдите к 2.

Список всех используемых делителей - это простые множители оригинала m.

Код:

-- | prime factors
--
-- >>> factors 13
-- [13]
-- >>> factors 16
-- [2,2,2,2]
-- >>> factors 60
-- [2,2,3,5]
--
factors :: Int -> [Int]
factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

-- | primes
--
-- >>> take 10 primes
-- [2,3,5,7,11,13,17,19,23,29]
--
primes :: [Int]
primes = f [2..] where f (p : ns) = p : f [n | n <- ns, n `mod` p /= 0]

Update:

Этот код замены повышает производительность, избегая ненужных оценок:

factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m < n ^ 2 = [m]   -- stop early
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

primes также можно ускорить, как указано в комментарий Will Ness:

primes = 2 : filter (\n-> head (factors n) == n) [3,5..]

Ответ 3

Это хорошо продуманная и простая в понимании реализация, в которой isPrime и primes определены рекурсивно, а primes будет кэшироваться по умолчанию. primeFactors определение - это просто правильное использование primes, результат будет содержать непрерывные дублированные числа, эта функция позволяет легко подсчитать количество каждого фактора с помощью (map (head &&& length) . group) и легко его уникально через (map head . group):

isPrime :: Int -> Bool
primes :: [Int]

isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<= n) . (^ 2)) $ primes
primes = 2 : filter isPrime [3..]

primeFactors :: Int -> [Int]
primeFactors n = iter n primes where
    iter n (p:_) | n < p^2 = [n | n > 1]
    iter n [email protected](p:ps') =
        let (d, r) = n `divMod` p
        in if r == 0 then p : iter d ps else iter n ps'

И использование:

> import Data.List
> import Control.Arrow

> primeFactors 12312
[2,2,2,3,3,3,3,19]

> (map (head &&& length) . group) (primeFactors 12312)
[(2,3),(3,4),(19,1)]

> (map head . group) (primeFactors 12312)
[2,3,19]

Ответ 4

Haskell позволяет создавать бесконечные списки, которые являются взаимно рекурсивными. Пусть это выгодно.

Сначала создайте вспомогательную функцию, которая как можно больше делит число на другое. Нам понадобится, когда мы найдем фактор, чтобы полностью исключить его из числа.

import Data.Maybe (mapMaybe)

-- Divide the first argument as many times as possible by the second one.
divFully :: Integer -> Integer -> Integer
divFully n q | n `mod` q == 0   = divFully (n `div` q) q
             | otherwise        = n

Далее, предполагая, что у нас есть список всех простых чисел, мы можем легко найти множители чисел, разделив его на все простые числа, меньшие квадратного корня из числа, и если число делится, отметив простое число.

-- | A lazy infinite list of non-trivial factors of all numbers.
factors :: [(Integer, [Integer])]
factors = (1, []) : (2, [2]) : map (\n -> (n, divisors primes n)) [3..]
  where
    divisors :: [Integer] -> Integer -> [Integer]
    divisors _ 1          = []   -- no more divisors
    divisors (p:ps) n
        | p^2 > n       = [n]  -- no more divisors, `n` must be prime
        | n' < n        = p : divisors ps n'    -- divides
        | otherwise     = divisors ps n'        -- doesn't divide
      where
        n' = divFully n p

И наоборот, когда у нас есть список всех факторов чисел, легко найти простые числа: они точно такие числа, единственным простым фактором которых является само число.

-- | A lazy infinite list of primes.
primes :: [Integer]
primes = mapMaybe isPrime factors
  where
    -- |  A number is prime if it only prime factor is the number itself.
    isPrime (n, [p]) | n == p  = Just p
    isPrime _                  = Nothing

Фокус в том, что мы начинаем список факторов вручную, и чтобы определить список простых факторов числа, нам нужны только числа меньше, чем его квадратный корень. Посмотрим, что произойдет, когда мы немного перечислим список факторов, и мы пытаемся вычислить список факторов из 3. Мы потребляем список простых чисел, беря 2 (которые можно вычислить из того, что мы дали вручную). Мы видим, что он не делит 3 и что, так как он больше квадратного корня из 3, то нет более возможных делителей 3. Поэтому список факторов для 3 равен [3]. Из этого можно вычислить, что 3 - другое простое. Etc.

Ответ 5

Я просто работал над этой проблемой. Здесь мое решение.

Две вспомогательные функции:

factors n = [x | x <- [1..n], mod n x == 0]
isPrime n = factors n == [1,n]

Затем, используя понимание списка, чтобы получить все основные факторы и сколько их.

prime_factors num = [(last $ takeWhile (\n -> (x^n) `elem` (factors num)) [1..], x) | x <- filter isPrime $ factors num]

где

x <- filter isPrime $ factors num

говорит мне, какие простые коэффициенты имеют заданное число, а

last $ takeWhile (\n -> (x^n) `elem` (factors num)) [1..]

говорит мне, сколько этого фактора.

<сильные > Примеры

> prime_factors 36    -- 36 = 4 * 9
[(2,2),(2,3)]

> prime_factors 1800  -- 1800 = 8 * 9 * 25
[(3,2),(2,3),(2,5)]

Ответ 6

более элегантный код ， используйте 2 и нечетные числа, чтобы разделить число.

factors' :: Integral t => t -> [t]
factors' n
  | n < 0 = factors' (-n)
  | n > 0 = if 1 == n
               then []
               else let fac = mfac n 2 in fac : factors' (n 'div' fac)
  where mfac m x
          | rem m x == 0 = x
          | x * x > m    = m
          | otherwise    = mfac m (if odd x then x + 2 else x + 1)

Ответ 7

Здесь моя версия. Не так кратко, как другие, но я думаю, что это очень читабельно и легко понять.

import Data.List

factor :: Int -> [Int]
factor n
  | n <= 1 = []
  | even n = 2 : factor(div n 2)
  | otherwise =
    let root = floor $ sqrt $ fromIntegral n
    in
      case find ((==) 0 . mod n) [3, 5.. root] of
        Nothing  -> [n]
        Just fac -> fac : factor(div n fac)