Проект Эйлера Задача 27 в F#
-
06-09-2019 - |
Вопрос
Я пытался проложить свой путь через Проблема 27 из проекта Эйлер, но этот, кажется, ставит меня в тупик.Во-первых, выполнение кода занимает слишком много времени (возможно, пару минут на моей машине, но, что более важно, он возвращает неправильный ответ, хотя я действительно не могу обнаружить ничего неправильного в алгоритме, просмотрев его некоторое время.
Вот мой текущий код для решения.
/// Checks number for primality.
let is_prime n =
[|1 .. 2 .. sqrt_int n|] |> Array.for_all (fun x -> n % x <> 0)
/// Memoizes a function.
let memoize f =
let cache = Dictionary<_, _>()
fun x ->
let found, res = cache.TryGetValue(x)
if found then
res
else
let res = f x
cache.[x] <- res
res
/// Problem 27
/// Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
let problem27 n =
let is_prime_mem = memoize is_prime
let range = [|-(n - 1) .. n - 1|]
let natural_nums = Seq.init_infinite (fun i -> i)
range |> Array.map (fun a -> (range |> Array.map (fun b ->
let formula n = n * n + a * n + b
let num_conseq_primes = natural_nums |> Seq.map (fun n -> (n, formula n))
|> Seq.find (fun (n, f) -> not (is_prime_mem f)) |> fst
(a * b, num_conseq_primes)) |> Array.max_by snd)) |> Array.max_by snd |> fst
printn_any (problem27 1000)
Любые советы о том, как а) заставить этот алгоритм действительно возвращать правильный ответ (я думаю, что я, по крайней мере, использую работоспособный подход) и б) повысить производительность, поскольку она явно превышает "правило одной минуты", изложенное в Project Euler FAQ.Я немного новичок в функциональном программировании, поэтому также был бы признателен за любой совет о том, как я мог бы рассмотреть проблему с учетом более функционального решения.
Решение
Два замечания:
Вы можете воспользоваться тем фактом, что
b
должно быть, простое.Это следует из того факта, что в задаче запрашивается самая длинная последовательность простых чисел дляn = 0, 1, 2, ...
Итак,formula(0)
должно быть , это просто с самого начала , ноformula(0) = b
, следовательно, b должно быть простым.Я не программист на F #, но мне кажется, что код вообще не пытается использовать n = 0.Это, конечно, не соответствует требованию проблемы о том, что
n
нужно начинать с0
, следовательно, вероятность того, что может быть получен правильный ответ, ничтожно мала.
Другие советы
Итак, после долгой проверки того, что все вспомогательные функции выполняют то, что должны, я, наконец, пришел к рабочему (и достаточно эффективному) решению.
Во-первых, is_prime является простым функция была совершенно неправильной (спасибо Дмитрию Новатчеву за то, что заставил меня взглянуть на это).Я не совсем уверен, как я пришел к функции, которую я опубликовал в исходном вопросе, но я предположил, что она работает, поскольку я использовал ее в предыдущих задачах.(Скорее всего, я просто подправил ее и с тех пор сломал.) В любом случае, рабочая версия этой функции (которая в решающей степени возвращает false для всех целых чисел меньше 2) такова:
/// Checks number for primality.
let is_prime n =
if n < 2 then false
else [|2 .. sqrt_int n|] |> Array.for_all (fun x -> n % x <> 0)
Основная функция была изменена на следующую:
/// Problem 27
/// Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
let problem27 n =
let is_prime_mem = memoize is_prime
let set_b = primes (int64 (n - 1)) |> List.to_array |> Array.map int
let set_a = [|-(n - 1) .. n - 1|]
let set_n = Seq.init_infinite (fun i -> i)
set_b |> Array.map (fun b -> (set_a |> Array.map (fun a ->
let formula n = n * n + a * n + b
let num_conseq_primes = set_n |> Seq.find (fun n -> not (is_prime_mem (formula n)))
(a * b, num_conseq_primes))
|> Array.max_by snd)) |> Array.max_by snd |> fst
Ключевым моментом здесь для увеличения скорости было сгенерировать только набор простых чисел от 1 до 1000 для значений b (используя простые числа функция, моя реализация метода Сита Эратосфена).Мне также удалось сделать этот код немного более кратким, устранив ненужный Seq.map.
Итак, я вполне доволен решением, которое у меня есть сейчас (это занимает чуть меньше секунды), хотя, конечно, любые дальнейшие предложения все равно будут приветствоваться...
Вы могли бы ускорить свою функцию "is_prime", используя вероятностный алгоритм.Одним из самых простых быстрых алгоритмов для этого является Миллер-Рабин алгоритм.
чтобы избавиться от половины ваших вычислений, вы также могли бы сделать массив возможным, поскольку он содержит только нечетные числа
мое сверхбыстрое решение на python: P
flag = [0]*204
primes = []
def ifc(n): return flag[n>>6]&(1<<((n>>1)&31))
def isc(n): flag[n>>6]|=(1<<((n>>1)&31))
def sieve():
for i in xrange(3, 114, 2):
if ifc(i) == 0:
for j in xrange(i*i, 12996, i<<1): isc(j)
def store():
primes.append(2)
for i in xrange(3, 1000, 2):
if ifc(i) == 0: primes.append(i)
def isprime(n):
if n < 2: return 0
if n == 2: return 1
if n & 1 == 0: return 0
if ifc(n) == 0: return 1
return 0
def main():
sieve()
store()
mmax, ret = 0, 0
for b in primes:
for a in xrange(-999, 1000, 2):
n = 1
while isprime(n*n + a*n + b): n += 1
if n > mmax: mmax, ret = n, a * b
print ret
main()