В сфере программирования простые числа занимают особое место благодаря своим уникальным свойствам и приложениям. Если вы знакомы с Haskell, функциональным языком программирования, известным своей элегантностью и выразительностью, вы будете рады изучить множество способов определить, является ли число простым. В этом сообщении блога мы рассмотрим несколько подходов к проверке простых чисел в Haskell, сопровождаемые простыми для понимания примерами кода. Итак, отправляемся в это увлекательное путешествие!

Метод 1: пробное деление
Метод пробного деления — один из самых простых способов проверить, является ли число простым. Он предполагает деление числа на все целые числа от 2 до квадратного корня числа и проверку на наличие остатка.

isPrime :: Int -> Bool
isPrime n
  | n < 2     = False
  | otherwise = all (\x -> n `mod` x /= 0) [2..isqrt n]
  where
    isqrt = floor . sqrt . fromIntegral

Метод 2: Решето Эратосфена
Решето Эратосфена — это древний алгоритм, который эффективно находит все простые числа до заданного предела. Применяя этот алгоритм, мы также можем определить, является ли конкретное число простым.

isPrime :: Int -> Bool
isPrime n
  | n < 2     = False
  | otherwise = primes !! n == n
  where
    primes = sieve [2..]
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

Метод 3: тест на простоту Миллера-Рабина
Тест на простоту Миллера-Рабина — это вероятностный алгоритм, широко используемый при работе с большими числами. Хотя иногда он может давать ложные срабатывания, он очень эффективен и часто используется на практике.

import System.Random
isPrime :: Int -> IO Bool
isPrime n
  | n < 2     = return False
  | otherwise = do
      witnesses <- getRandomWitnesses (n - 1) 10 -- Adjust the number of witnesses for desired accuracy
      return $ all (primalityTest n) witnesses
getRandomWitnesses :: Int -> Int -> IO [Int]
getRandomWitnesses _ 0 = return []
getRandomWitnesses n k = do
  witness <- randomRIO (2, n)
  witnesses <- getRandomWitnesses n (k - 1)
  return (witness : witnesses)
primalityTest :: Int -> Int -> Bool
primalityTest n a
  | x == 1 || x == n' = True
  | otherwise         = any (== n') powers
  where
    n' = n - 1
    (s, d) = determineSD n'
    x = powMod a d n
    powers = take s (iterate (\x -> (x * x) `mod` n) x)
determineSD :: Int -> (Int, Int)
determineSD n = go 0 n
  where
    go s d
      | even d    = go (s + 1) (d `div` 2)
      | otherwise = (s, d)
powMod :: Int -> Int -> Int -> Int
powMod x y m = go x y 1
  where
    go _ 0 res = res
    go x' y' res
      | even y'    = go ((x' * x') `mod` m) (y' `div` 2) res
      | otherwise  = go x' (y' - 1) ((res * x') `mod` m)

В этом сообщении блога мы рассмотрели три различных метода проверки того, является ли число простым в Haskell. Метод пробного деления прост и подходит для меньших чисел, а «Решето Эратосфена» превосходно справляется с поиском простых чисел до заданного предела. Наконец, тест на простоту Миллера-Рабина обеспечивает вероятностный, но эффективный способ проверки простоты больших чисел. Используя эти методы, вы можете уверенно обрабатывать простые числа в своих программах на Haskell.