프로젝트의 오일러 문제 27F#

Question

내가 하려고 했는데 작업을 통해 내 방식 문제 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)

하는 방법에 대한 조언 a)이 알고리즘을 실제로 정답(난에서 이상을 복용 가능한 접근 방식)및 b)성능 향상을 위해,그것을 명확하게 초과하는"한 분 규칙"설정 프로젝트에서 오일러 자주 묻는 질문에 있습니다.나의 비트 초보자를 프로그래밍,그래서 어떤 방법에 대한 조언도하는 문제로 더 많은 기능적인 솔루션을 마음에도 감사드립니다.

Answer 1

두 가지 발언 :

1. 당신은 그 사실을 활용할 수 있습니다 b 주요해야합니다. 이것은 문제가 가장 긴 프라임 시퀀스를 요구한다는 사실에서 비롯됩니다. n = 0, 1, 2, ... 그래서, formula(0) 처음부터 시작해야하지만 formula(0) = b, 따라서 B가 프라임이어야합니다.

2. 나는 F# 프로그래머는 아니지만 코드가 전혀 n = 0을 시도하지 않는 것 같습니다.. 물론 이것은 문제의 요구 사항을 충족하지 않습니다. n 시작해야합니다 0, 따라서 정답이 생성 될 수있는 소홀한 기회가 있습니다.

Answer 2

오른쪽의 많은 후,검사는 모든 도우미 기능을 하고 있던 그들은 무엇을 해야,나는 마지막으로 도달 작업(고 합리적으로 효율적인)솔루션입니다.

첫째, is_prime 기능을 완전히 잘못(덕분에 Dimitre Novatchev 만들기 위한 날에 보는).나는 확실하지 않는 방법에 도착했을 때 기능에 게시 원래의 질문,하지만 난다고 생각하고 그것 때문에 작업 내용 이전에 문제입니다.(대부분,나는 그냥 그것을 변화를 줬고 그것을 끊습니다.) 어쨌든,작동 버전의 이수(는 결정에 대해 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.지도입니다.

그래서 나는 매우 행복하는 방법을 지속적으로 연구하는 지금 있는(그것은 단지에서 두 번째),하지만 물론 더 제안이 여전히 환영합니다...

Answer 3

확률 적 알고리즘을 사용하여 "IS_PRIME"기능 속도를 높일 수 있습니다. 이것에 대한 가장 쉬운 빠른 알고리즘 중 하나는 밀러-라빈 연산.

Answer 4

계산의 절반을 제거하려면 가능한 A의 배열을 홀수 만 포함시킬 수도 있습니다.

Answer 5

나의 초고속 파이썬 솔루션 : 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()