Может время выполнения этого генератора простого числа быть улучшенным?

Я написал императивную версию, которая быстрее. Может быть невозможно написать сито Eratosthenhes в чистом функциональном способе для достижения такой же скорости, поскольку у вас должно быть двоичное состояние для каждого номера.

let generatePrimes max=
    let p = Array.create (max+1) true
    let rec filter i step = 
        if i <= max then 
            p.[i] <- false
            filter (i+step) step
    {2..int (sqrt (float max))} |> Seq.map (fun i->filter (i+i) i) |> Seq.length |> ignore
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray

Просто для знакомых, давайте посмотрим на эта страница .

PI (X) - это главная функция подсчета, она возвращает количество простых простых простых простых простусов ниже x. Вы можете приблизить PI (X), используя следующие неравенства:

(x/log x)(1 + 0.992/log x) < pi(x) < (x/log x)(1 + 1.2762/log x) 
// The upper bound holds for all x > 1

P (x) - первичная функция nth, которая может быть аппроксимирована с использованием:

n ln n + n ln ln n - n < p(n) < n ln n + n ln ln n
// for n >= 6

с этим в виду, вот очень быстрый генератор который вычисляет первые N простые числа, где каждый элемент при индексе I равно p (i) . Итак, если мы хотим завершить наш массив в простые простыни ниже 2 000 000, мы используем неравенство верхнего уровня для простого подсчета:

let rec is_prime (primes : int[]) i testPrime maxFactor =
    if primes.[i] > maxFactor then true
    else
        if testPrime % primes.[i] = 0 then false
        else is_prime primes (i + 1) testPrime maxFactor

let rec prime_n (primes : int[]) primeCount testPrime tog =
    if primeCount < primes.Length then
        let primeCount' =
            if is_prime primes 2 testPrime (float testPrime |> sqrt |> int) then
                primes.[primeCount] <- testPrime
                primeCount + 1
            else
                primeCount
        prime_n primes primeCount' (testPrime + tog) (6 - tog)

let getPrimes upTo =
    let x = float upTo
    let arraySize = int <| (x / log x) * (1.0 + 1.2762 / log x)
    let primes = Array.zeroCreate (max arraySize 3)
    primes.[0] <- 2
    primes.[1] <- 3
    primes.[2] <- 5

    prime_n primes 3 7 4
    primes

Cool! Так как быстро это? На моем четырехъядерном ядре 3,2 ГГц я получаю следующее в FSI:

> let primes = getPrimes 2000000;;
Real: 00:00:00.534, CPU: 00:00:00.546, GC gen0: 0, gen1: 0, gen2: 0

val primes : int [] =
  [|2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
    73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
    157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
    239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
    331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
    421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503;
    509; 521; 523; 541; ...|]

> printfn "total primes: %i. Last prime: %i" (primes.Length - 1) primes.[primes.Length - 1];;
total primes: 149973. Last prime: 2014853

, так что все простые простые простые простые простые простые промирели в менее чем за полторы:)

Редактировать: обновленная версия ниже, использует меньше памяти и быстрее

Иногда приятно быть в состоянии мутировать вещи. Вот А, по общему признанию, версию, которая торгует памятью для скорости. Поскольку эта нить получилась, чтобы провести приятную коллекцию простых генерирующих функций в F #, я подумал, что было бы приятно в любом случае. Использование Bitarray сохраняет память в проверке.

open System.Collections

let getPrimes nmax =
    let sieve = new BitArray(nmax+1, true)
    let result = new ResizeArray<int>(nmax/10)
    let upper = int (sqrt (float nmax))   
    result.Add(2)

    let mutable n = 3
    while n <= nmax do
       if sieve.[n] then
           if n<=upper then 
               let mutable i = n
               while i <= nmax do sieve.[i] <- false; i <- i + n
           result.Add n
       n <- n + 2
    result

Обновление:

Код выше может быть оптимизирован дальше: поскольку он использует только нечетные индексы в сите, битарай может быть уменьшен до половины размера путем индексации нечетного n как 2m + 1. Новая версия также быстрее:

let getPrimes2 nmax =
    let sieve = new BitArray((nmax/2)+1, true)
    let result = new ResizeArray<int>(nmax/10)
    let upper = int (sqrt (float nmax))   
    if nmax>1 then result.Add(2) //fixes a subtle bug for nmax < 2

    let mutable m = 1
    while 2*m+1 <= nmax do
       if sieve.[m] then
           let n = 2*m+1
           if n <= upper then 
               let mutable i = m
               while 2*i < nmax do sieve.[i] <- false; i <- i + n
           result.Add n
       m <- m + 1
    result

Timing (Intel Core Duo 2.33 ГГц):

> getPrimes 2000000 |> Seq.length;;
Real: 00:00:00.037, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 148933
> getPrimes2 2000000 |> Seq.length;;
Real: 00:00:00.026, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 148933

Обязательная версия, размещенная Инь, очень быстрая. На моей машине это также около 0.5sec. Однако, если вы хотите написать простое функциональное решение, вы можете просто написать следующее:

let isPrime(n) =
  let ms = int64(sqrt(float(n)))
  let rec isPrimeUtil(m) =
    if m > ms then true
    elif n % m = 0L then false
    else isPrimeUtil(m + 1L)
  (n > 1L) && isPrimeUtil(2L)

[ 1L .. 2000000L ] |> List.filter isPrime

Это просто проверяет, является ли число простым для всех чисел до 1 милиона. Он не использует никаких сложных алгоритмов (на самом деле забавно, что простейшее решение часто бывает достаточно хорошим!). На моей машине, ваша обновленная версия работает около 11 секунд, а это около 2 секунд.

Более интересно, что это очень легко распараллелить. Если вы используете PLINQ, вы можете написать версию ниже, и она будет работать почти в 2 раза быстрее на двух ядрах. Это означает, что на четырехъядерном ядре она может работать так же быстро, как и самое быстрое решение из всех приведенных здесь ответов, но с минимальными затратами на программирование :-). (конечно, использование четырех ядер не экологично, но... ну)

[ 1L .. 2000000L ] |> PSeq.ofSeq |> PSeq.filter isPrime |> List.ofSeq

Функции PSeq являются обертками для PLINQ, которые я создал для своей книги (это делает использование PLINQ из F# более естественным). Они доступны в исходном коде для Гл. 14.