-- code skipped
RK>

primes.hs:43:8: parse error (possibly incorrect indentation)

ERROR file:{Hugs}\packages\hugsbase\Hugs\ST.hs:51 — Syntax error in type expression (unexpected `.')

  NB. собственно сам глагол вычисляющий нужное нам количество
   cntPrimesFromTo =. -/@:(_1&p:)@|.
  NB. его использование
   cntPrimesFromTo 100000000 120000000
1080193
  NB. замер производительности, в секундах!
   6!:2 'cntPrimesFromTo 100000000 120000000'
0.0616224

  NB. глагол вычисляющий список простых чисел в заданном интервале
   primesFromTo =. [: p: ({.+i.@({:-{.))@(_1&p:)
  NB. его использование
   primesFromTo 100000000 120000000
100000007 100000037 100000039 100000049 100000073 100000081 100000123 100000127 100000193 100000213 100000217 100000223 100000231 100000237 100000259 100000267 100000279 100000357 100000379 100000393 100000399 100000421 100000429 100000463 100000469 100000...
  NB. длина возвращаемого им списка
   # primesFromTo 100000000 120000000
1080193
  NB. замер производительности
   6!:2 '# primesFromTo 100000000 120000000'
0.316999

sqrtInt x
    | x<0 = error "sqrt negative number"
    | otherwise = rec 1
    where rec y
              | y==avg = y
              | y==avg-1 = if avg*avg==x then avg else y
              | otherwise = rec avg
              where avg = (y+x`quot`y)`quot`2

primes@(_:tpr) = 2 : 3 : (concatMap (uncurry genMap) $ zip primes tpr)

-- эта функция фактически является оптимизацией genMap' (см. ниже)
genMap 2 3 = [5,7] -- special case, even p0^2
genMap p0 p1 = arrayFilter lo lo' $ accum (flip const)
    (listArray (lo', hi'-1) $ repeat True :: UArray Integer Bool)
    [ (j, False)
    | i <- takeWhile (<p1) $ tail primes
    , j <- takeWhile (<hi') $ iterate (+i) $
        (i*(incIfEven $ correctRem $ lo `quotRem` i)) `quot` 2
    ]
    where
    lo = p0^2; hi = p1^2
    lo' = lo `quot` 2; hi' = hi `quot` 2
    correctRem (q,0) = q
    correctRem (q,_) = q+1
    incIfEven n
        | even n = n+1
        | otherwise = n
    arrayFilter n i a
        | i==hi' = []
        | a!i = n : arrayFilter (n+2) (i+1) a
        | otherwise = arrayFilter (n+2) (i+1) a

-- так выглядел первоначальный вариант genMap с фильтрацией списков:
genMap' 2 3 = [5,7] -- специальный случай, 2^2=4 - четное число
genMap' p0 p1 = -- реализация решета Эратосфена на ленивых списках
    foldl -- свертка слева списка потенциальных простых чисел со списком уже известных простых чисел
        (\l i -> fun l i (i*(quot lo i))) -- применение функции, отфильтровывающей составные числа
        [lo,lo+2..hi-2] -- список нечетных чисел от p0^2 до (p1^2-2) (из него будут вычеркиваться составные числа)
        (takeWhile (<p1) $ tail primes') -- список простых чисел меньших p1
    where
    lo = p0^2; hi = p1^2
    -- fun вычеркивает из списка все числа кратные d, начиная с c
    fun [] _ _ = []
    fun l@(h:t) d c
        | h==c = fun t d (c+d)
        | h>c = fun l d (c+d)
        | otherwise = h : fun t d c

primes'@(_:tpr) = 2 : 3 : (concatMap (uncurry genMap') $ zip primes' tpr)

ie>В любом случае, повторить твой вариант на Немерле хотелось бы, но разобраться бы сперва

RK>Все просто на самом деле

RK>primes@(_:tpr) = 2 : 3 : (concatMap (uncurry genMap) $ zip primes tpr)

RK>-- эта функция фактически является оптимизацией genMap' (см. ниже)
RK>genMap 2 3 = [5,7] -- special case, even p0^2
RK>genMap p0 p1 = arrayFilter lo lo' $ accum (flip const)
RK>    (listArray (lo', hi'-1) $ repeat True :: UArray Integer Bool)
RK>    [ (j, False)
RK>    | i <- takeWhile (<p1) $ tail primes
RK>    , j <- takeWhile (<hi') $ iterate (+i) $
RK>        (i*(incIfEven $ correctRem $ lo `quotRem` i)) `quot` 2
RK>    ]
RK>    where
RK>    lo = p0^2; hi = p1^2
RK>    lo' = lo `quot` 2; hi' = hi `quot` 2
RK>    correctRem (q,0) = q
RK>    correctRem (q,_) = q+1
RK>    incIfEven n
RK>        | even n = n+1
RK>        | otherwise = n
RK>    arrayFilter n i a
RK>        | i==hi' = []
RK>        | a!i = n : arrayFilter (n+2) (i+1) a
RK>        | otherwise = arrayFilter (n+2) (i+1) a

RK>-- так выглядел первоначальный вариант genMap с фильтрацией списков:
...
RK>

RK>Ага, а если на C++ мой алгоритм переписать?

Сможешь написать функцию, подобную primesFromTo, только без использования ленивости?

ie>>В любом случае, повторить твой вариант на Немерле хотелось бы, но разобраться бы сперва

RK>Ну теперь совсем просто будет

Сможешь написать функцию, подобную primesFromTo, только без использования ленивости?
primesFromTo принимает min и max границы и выдает список всех простых чисел в интервале.

Тут видишь в чем дело, вся эта ветка — спор "где нагляднее". Выдвинули предположение, о том, что ленивость в некоторых случаях делает код более наглядным, при этом можно не особо пролететь в производительности. Что ты собственно и показал своим примером. [...] Т.о. я сделал предположение, что это быстродействие достигается за счет ленивости.

using System
using System.Collections.Generic
using System.Console
using System.Diagnostics
using Nemerle.Utility

def _primes = List.[int]([3])

def primesFromTo(__from, __to, lst)

    def doWhenEven = (x,f) => if (x%2 == 0) f(x) else x
    def from = doWhenEven(__from, _+1)
    def to   = doWhenEven(__to, _-1)
    def sqrt = x => Math.Ceiling(Math.Sqrt(x)) :> int
    when (sqrt(to) > 5)
        primesFromTo(5, sqrt(to), _primes)

    def diff = (to - from)/2
    def arr = array.[bool](diff)
    def num = x => x*2+from
    mutable sindex
    def findIndex(p, i) { if (num(i)%p == 0) i else findIndex(p, i+1) }
    def eratosthenes = (p, i) => $[i,i+p..arr.Length-1].Iter(j => arr[j] = true) // (**)
    def addCulculated = (s, e) => $[s..e-1].Filter(j => !arr[j]).Iter(j => lst.Add(num(j))) // (++)

    for (mutable i; i < _primes.Count; i++)
        def p = _primes[i]
        def sq = x => Math.Pow(x,2) :> int
        when (num(sindex) < sq(p))
          def d = (sq(p) - num(sindex))/2
          addCulculated(sindex, Math.Min(sindex+d, diff))
          sindex += d
        eratosthenes(p, findIndex(p, sindex))
    addCulculated(sindex, diff)

def sw = Stopwatch()
def lst = List.[int]()
sw.Start()
primesFromTo(100000000, 120000000, lst)
sw.Stop()
WriteLine($"Elapsed: $(sw.Elapsed.TotalSeconds) ;; Count: $(lst.Count)")

>out.exe
Elapsed: 8.0298764 ;; Count: 1080193

RK>Ну будет не так кратко, но что быстрее в 4-8 раз — почти не сомневаюсь

    def eratosthenes = (p, i) => 
        foreach (j in [i,i+p..arr.Length-1])
            arr[j] = true;
    def addCulculated = (s, e) => 
        foreach (j in [s..e-1])
            when (!arr[j])
                lst.Add(num(j));

>out.exe
Elapsed: 1.1022526 ;; Count: 1080193