Проект Эйлера Задача 27 в F #

Question

Я пытался проработать Проблема 27 Project Euler, но этот, кажется, озадачивает меня. Во-первых, выполнение кода занимает слишком много времени (возможно, пару минут на моей машине, но, что более важно, он возвращает неправильный ответ, хотя я действительно не могу обнаружить что-то не так с алгоритмом после некоторого просмотра его) .

Вот мой текущий код для решения.

/// 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)

Любые советы о том, как: а) заставить этот алгоритм на самом деле возвращать правильный ответ (я думаю, что я, по крайней мере, использую работоспособный подход) и б) улучшить производительность, так как она явно превышает "правило одной минуты", изложенное в проекте Euler FAQ. Я немного новичок в функциональном программировании, поэтому любые советы о том, как я могу рассмотреть проблему с более функциональным решением, также будут оценены.

Answer 1

Два замечания:

1. Вы можете воспользоваться тем, что b должно быть простым . Это следует из того факта, что проблема требует самой длинной последовательности простых чисел для n = 0, 1, 2, ... Итак, formula(0) должно быть простым для начала, но formula(0) = b, следовательно, b должно быть простым.

2. Я не программист на F #, но мне кажется, что код вообще не пытается n = 0 . Это, конечно, не соответствует требованию проблемы, согласно которому n должен начинаться с 0, поэтому вероятность того, что правильный ответ может быть получен, ничтожна.

Answer 2

Правильно, после тщательной проверки того, что все вспомогательные функции выполняют то, что должны, я наконец-то нашел работающее (и достаточно эффективное) решение.

Во-первых, функция 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 (используя функцию primes , моя реализация Sieve of Метод Эратосфена). Мне также удалось сделать этот код немного более лаконичным, исключив ненужный Seq.map.

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

Answer 3

Вы можете ускорить свою функцию is_prime, используя вероятностный алгоритм. Один из самых простых быстрых алгоритмов для этого - алгоритм Миллера-Рабина .

Answer 4

мое сверхбыстрое решение 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()

Answer 5

чтобы избавиться от половины ваших вычислений, вы также можете сделать массив возможных а только нечетными числами