Хаскелл Прайм-тестирование путаницы

Question

Так что я совершенно новичок в Хаскеле, надеюсь, это не так уж и много. В любом случае я пытался создать функцию, чтобы определить, является ли число простым. Основная идея заключается в следующем: если дано число, посмотрите, делится ли оно на любое другое число, меньшее его. Если это так, верните false. Если нет, это просто, верните истину. Код (который, как известно, работает) выглядит так:

divisible :: Integer -> Integer -> Bool
divisible x 2 = even x
divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))
isPrime :: Integer -> Bool
isPrime x = not (even x) && not (divisible x (x-1))

Производит:

ghci> isPrime 9
False
ghci> isPrime 13
True

То, что я хотел бы сделать, это немного оптимизировать это, так как мне нужно только проверять значения, меньшие или равные sqrt(x). Проблема в том, что когда я пытаюсь это реализовать, все становится сумасшедшим:

isPrime x = not (even x) && not (divisible x (ceiling(sqrt(fromIntegral(x-1)))))

Помимо того, что это выглядит ужасно (я сказал, что я новичок), это не дает правильный результат:

ghci> isPrime 9
False
ghci> isPrime 13
False

Я пытаюсь выяснить, что изменилось, потому что:

ghci> ceiling(sqrt(13))
4

Кажется, дает мне правильный номер. Я знаю, что это небольшая проблема, но я серьезно запутался...

Answer 1

Вы перепутали свои условия:

divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))

должно быть

divisible x y = (x `mod` y) == 0 || divisible x (y-1)

для теста на работу.

Как и ваш divisible функция расширяется, например,

divisible 21 5 = (21 `mod` 5 /= 0) && not (divisible 21 4)
               = (21 `mod` 5 /= 0) && not ((21 `mod` 4 /= 0) && not (divisible 21 3))
               = not ((21 `mod` 4 /= 0) && not ((21 `mod` 3 /= 0) && not (divisible 21 2)))
               = not (True && not (False && not (divisible 21 3)))
               = not (not False)
               = False

поскольку 21 `mod` 3 == 0, а также isPrime 21 оценивает True с квадратным корнем связаны.

Тем не менее, я получаю

*StrangePrime> isPrime 9
True
*StrangePrime> isPrime 13
True

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

Без квадратного корня это работало для нечетных чисел, потому что разница между нечетным составным и любым из его делителей всегда четна. Разворачивание divisible несколько шагов для n = p*m, где p наименьший простой фактор нечетного композита n, мы видим

divisible n (n-1) = n `mod` (n-1) /= 0 && not (divisible n (n-2))
                  = not (divisible n (n-2))
                  = not (n `mod` (n-2) /= 0 && not (divisible n (n-3)))
                  = not (not (divisible n (n-3)))
                  = not^2 (divisible n (n-3))

и индуктивно

divisible n (n-1) = not^(k-1) (divisible n (n-k))

если нет делителей n больше, чем n-k, Теперь, в описанной выше ситуации, самый большой делитель n является m = n - (p-1)*mИтак, мы получаем

divisible n (n-1) = not^((p-1)*m-1) (divisible n m)
                  = not^((p-1)*m-1) (n `mod` m /= 0 && not (...))

Но n `mod` m == 0Итак, мы имеем

divisible n (n-1) = not^((p-1)*m-1) False

поскольку p странно, p-1 четный, а значит, и так (p-1)*mтак что в целом у нас есть нечетное число nots, который такой же, как один not, давая

divisible n (n-1) = True
isPrime n = not (even n) && not (divisible n (n-1)) = True && not True = False

Если p нечетное простое число, разворачивается divisible p (p-1) = not^(p-3) (divisible p (p - (p-2))), p-3 даже, divisible p 2 является even p, который False,

В общем, рассмотрим divisible n s на нечетное n, и разреши d быть самым большим делителем n не превышающий s, если n является составным, или d = 2 если n прост. Разворачивание divisible n s все еще продолжается так же

divisible n s = not^k (divisible n (s-k))

в то время как делитель не был найден и s-k > 2, Так в случае с композитом n, мы нашли

divisible n s = not^(s-d) (divisible n d)
              = not^(s-d) (n `mod` d /= 0 && not (...))
              = not^(s-d) False
              = odd (s-d)
              = even s     -- since d is odd, as a divisor of an odd number

и в случае нечетного простого n,

divisible n s = not^(s-2) (divisible n 2)
              = not^(s-2) (even n)
              = not^(s-2) False
              = odd s

Так divisible n s измеряет соотношение расстояния s к следующему меньшему делителю n или до 2, в зависимости от того, что больше. когда s было n-1, отправная точка всегда была ровной, поэтому все получилось правильно, но ceiling (sqrt (fromIntegral (n-1))) может быть нечетным, и в этом случае результаты переворачиваются, а композиты объявляются простыми и наоборот.

Вы можете сделать свой divisible Функция работает для проверки простоты нечетных чисел с квадратным корнем, если вы убедитесь, что первый вызов получает четный второй аргумент (так что если ceiling (sqrt (fromIntegral (n-1))) странно, начать с ceiling (sqrt (fromIntegral (n-1))) + 1), но логика этой функции сбивает с толку, и ее имя неправильно описывает результаты.

Более идиоматический способ написать это будет

isPrime n = and [n `mod` k /= 0 | k <- [2 .. ceiling (sqrt $ fromIntegral n)]]

Тест становится более эффективным, когда пропускаются делители-кандидаты, которые, как известно, не являются делителями из предыдущих тестов, легко пропускают все четные числа, кроме 2,

isPrime 2 = True
isPrime n = all ((/= 0) . (n `mod`)) (2 : [3, 5 .. ceiling (sqrt (fromIntegral n))])

немного более сложным, но все же более эффективным также пропускает кратные 3

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:scanl (+) 5 (cycle [2,4])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))

В том же духе можно исключить кратные числа более мелких простых чисел из пробных делителей, каждый из которых получает небольшую эффективность, но за счет более сложного колеса, например, устранение кратных 5 приводит к

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:5: scanl (+) 7 (cycle [4,2,4,2,4,6,2,6])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))

Answer 2

Вот как я это сделаю:

divisibleBy :: (Integral a) => a -> a -> Bool
divisibleBy x y = mod x y == 0

isPrime :: (Integral a) => a -> Bool
isPrime x = or $ map (divisibleBy x) [2..(x-1)]

divisibleBy это простой тест делимости. isPrime выполняет этот тест для всех целых чисел от 1 до x, возвращая true, если x делится на любое из этих целых чисел. Вы можете изменить верхнюю границу на корень x, как вы сделали в своем коде, но в противном случае это работает.