代码之家 › 专栏 › 技术社区 › Noldorin

F中的Project Euler问题27#

primes functional-programming f#

1

Noldorin · 技术社区 · 16 年前

我一直在努力工作 Problem 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)

5 回复 | 直到 10 年前

1

7

Dimitre Novatchev 16 年前

b 必须是质数 n = 0, 1, 2, ... 所以, formula(0) formula(0) = b 因此,b必须是质数。
我不是F#程序员,但是当然,这并不符合问题的要求 n 0 ,因此,产生正确答案的可能性可以忽略不计。

2

3

Noldorin 16 年前

是的,在检查了所有辅助函数都在做它们应该做的事情之后,我终于找到了一个可行的(并且相当有效的)解决方案。

首先 is_pime

/// 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使这段代码稍微简洁一些。

所以,我对我现在的解决方案很满意(只需要不到一秒钟的时间),当然,任何进一步的建议都是受欢迎的。..

3

1

Brian 16 年前

你可以通过使用概率算法来加速你的“is_prime”函数。最简单的快速算法之一是 Miller-Rabin

4

-1

LDomagala 16 年前

5

-3

Zobayer 14 年前

我的超高速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()