[Haskell] Гипотеза Гольдбаха

 
0
 
Functional languages
ava
Joil | 08.11.2008, 14:38
Всем привет!
Есть такая задача:
Гипотеза Гольдбаха: Любое четное число > 2 представимо в виде суммы двух простых чисел.
Напишите функцию f m :: Integer -> Bool, проверяющую гипотезу Гольдбаха для всех четных чисел, больших 2 и меньших m.

Вот, какие есть вункции:

factors :: Integer -> [Integer]
--функция фычисляет список всех делителей числа
factors n = [k | k <- [1..n], n `mod` k == 0]

isprime :: Integer -> Bool
--функция определяет является ли число простым
isprime n = factors n == [1, n]

primesupto :: Integer -> [Integer]
функция возвращает  список, содержащий все простые числа до числа n включительно
primesupto n = [k | k <- [3..n], isprime k]

Что делать дальше, пока не могу сообразить...
Буду благодарен за любую помощь!!!
Comments (1)
ava
Shaggie | 18.11.2008, 08:32 #
Цитата (Joil @  8.11.2008,  14:38 findReferencedText)
Гипотеза Гольдбаха: Любое четное число > 2 представимо в виде суммы двух простых чисел.

Напишите функцию f m :: Integer -> Bool, проверяющую гипотезу Гольдбаха для всех четных чисел, больших 2 и меньших m.


Смотри. Функция должна 1) проверять, что число больше двух, иначе возвращать False; 2) проверять, что число чётное, иначе возвращать False; 3) для любого числа x, проходящего проверку, получать два списка простых чисел от 1 до x, получать список всех возможных сложений элементов первого списка с элементам второго списка (итог - суммы двух простых чисел), и проверять вхождение элемента x в полученном списке.

m   :: Integer -> Bool
m x |  x < 3 = False
    |  odd x = False
    |  otherwise = x `elem` [y + z | y <- primesupto x, z <- primesupto x]


P.S. Некоторые детали реализации.
1) Функция primesupto реализована не совсем верно, она должна проверять на простоту числа в списке не [3..n], а [1..n], т.к. 1 и 2 тоже простые числа. Проверка для гипотезы Гольдбаха вставляется в финальное m.
2) Функция isprime вернёт неправильный результат для числа 1, которое, несомненно, тоже является простым, так как ожидает, что в списке будет больше одного элемента. Корректнее было бы переписать её таким образом:

isprime   :: Integer -> Bool
isprime n |  factors n == [1] = True
          |  otherwise = factors n == [1, n]


Hope it'll help.

added later:
Как вариант, можно не возвращать False на x < 3 и odd x, а выбрасывать error с ругательством, ну это уже не важно - смотри как тебе больше нравится.
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Shaggie   Joil
advanced
Submit