let addprime arr n size = fold (fun a i -> set a (i*n)) [2..(size/n)] arr
let sieve size = fold (fun a i -> if get a i then addprime a i size else a) [2..size] (make size true)

def qsort(aList): 
        if not aList: 
                return [] 
        ltList=[y for y in aList[1:] if y<aList[0]] 
        gtList=[y for y in aList[1:] if y>=aList[0]] 
        return qsort(ltList)+[aList[0]]+qsort(gtList)

N_>main = putStr (show (filter primes [1..100]))
N_>

    unsigned x=1;
    timer_t timer;

    unsigned size=1000000000;
    std::vector<bool> is_prime(size, true);//помечаем все числа как простые
    for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число
        if(is_prime[i])
        {
            //i очередное простое число
            if(i>x)//иначе вывод становится ОЧЕНЬ узким местом
            {
                std::cout<<i<<" "<<timer.time()<<"\n";
                x<<=1;
            }
            for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все числа кратные данному числу
                is_prime[n]=false;
        }
    std::cout<<timer.time()<<"\n";

2 0.259567
3 2.23898
5 3.56067
11 4.92444
17 5.60239
37 6.54752
67 7.292
131 8.47562
257 10.5407
521 14.3472
1031 19.2141
2053 24.9814
4099 30.7079
8209 36.4478
16411 42.7149
32771 49.6374
65537 56.8574
131101 63.8289
262147 70.5661
524309 76.7928
1048583 82.2505
2097169 87.0388
4194319 91.121
8388617 94.4375
16777259 96.9167
33554467 98.4748
67108879 99.433
134217757 100.051
268435459 100.865
536870923 102.164
104.226

G>Кстати, слепенький я наверно. Ну не вижу я цикла for в твоем коде. А вот list comprehensions вижу, как и отсутствие побочных эффектов.

ltList=[y for y in aList[1:] if y<aList[0]]

ltList = []
for y in aList[1:] :
    if y<aList[0]: ltList.append(y)

G>Что характерно, если ты добавишь в любой язык встроенные списки так, как это сделано в современных ФЯ, то на нем сразу станет удобно писать в функциональном стиле. Одного не понимаю, каким именно образом это порочит "светлую идею" ФЯ?

int main()
{
    int NUM = 10;
    const unsigned size=8192;
    static char flags[size + 1];
    int count = 0;

    while (NUM--) 
    {
        count = 0;
        for (unsigned i=2; i <= size; i++) 
            flags[i] = 1;
        for (unsigned i=2; i <= size; i++) 
            if (flags[i]) 
            {
                // remove all multiples of prime: i
                for (unsigned k=i+i; k <= size; k+=i) 
                    flags[k] = 0;
                count++;
            }
    }
    printf("Count: %d\n", count);
}

_main    PROC NEAR                    ; COMDAT

; 4    : {

    push    ebx
    push    esi
    push    edi

; 5    :     int NUM = 10;

    mov    ebx, 10                    ; 0000000aH
    xor    edx, edx
    npad    6
$L64207:

; 11   :     {
; 12   :         count = 0;
; 13   :         for (unsigned i=2; i <= size; i++) 
; 14   :             flags[i] = 1;

    mov    ecx, 2047                ; 000007ffH
    mov    eax, 16843009                ; 01010101H
    mov    edi, OFFSET FLAT:?flags@?1??main@@9@4PADA+2
    rep stosd
    stosw
    xor    esi, esi
    stosb

; 15   :         for (unsigned i=2; i <= size; i++) 

    mov    ecx, 2
    npad    5
$L64214:

; 16   :             if (flags[i]) 

    cmp    BYTE PTR ?flags@?1??main@@9@4PADA[ecx], dl
    je    SHORT $L64215

; 17   :             {
; 18   :                 // remove all multiples of prime: i
; 19   :                 for (unsigned k=i+i; k <= size; k+=i) 

    cmp    ecx, 4096                ; 00001000H
    lea    eax, DWORD PTR [ecx+ecx]
    ja    SHORT $L64221
$L64219:

; 20   :                     flags[k] = 0;

    mov    BYTE PTR ?flags@?1??main@@9@4PADA[eax], dl
    add    eax, ecx
    cmp    eax, 8192                ; 00002000H
    jbe    SHORT $L64219
$L64221:

; 21   :                 count++;

    inc    esi
$L64215:

; 15   :         for (unsigned i=2; i <= size; i++) 

    inc    ecx
    cmp    ecx, 8192                ; 00002000H
    jbe    SHORT $L64214

; 6    :     const unsigned size=8192;
; 7    :     static char flags[size + 1];
; 8    :     int count = 0;
; 9    : 
; 10   :     while (NUM--) 

    dec    ebx
    jne    SHORT $L64207

; 22   :             }
; 23   :     }
; 24   :     printf("Count: %d\n", count);

    push    esi
    push    OFFSET FLAT:??_C@_0L@NKLBHBJO@Count?3?5?$CFd?6?$AA@
    call    _printf
    add    esp, 8
    pop    edi
    pop    esi

; 25   : }

    xor    eax, eax
    pop    ebx
    ret    0
_main    ENDP

    .intel_syntax
    .file    "sieve2.cpp"
    .def    ___main;    .scl    2;    .type    32;    .endef
.lcomm _ZZ4mainE5flags,8208
    .text
LC0:
    .ascii "Count: %d\12\0"
    .align 2
    .p2align 4,,15
.globl _main
    .def    _main;    .scl    2;    .type    32;    .endef
_main:
LFB1:
    push    ebp
LCFI0:
    xor    eax, eax
    mov    ebp, esp
LCFI1:
    push    ebx
LCFI2:
    mov    ebx, 9
    push    edx
    and    esp, -16
    call    __alloca
    call    ___main
L21:
    xor    ecx, ecx
    mov    eax, 2
    .p2align 4,,7
L9:
    mov    BYTE PTR _ZZ4mainE5flags[eax], 1
    inc    eax
    cmp    eax, 8192
    jbe    L9
    mov    edx, 2
    .p2align 4,,7
L20:
    cmp    BYTE PTR _ZZ4mainE5flags[edx], 0
    je    L12
    lea    eax, [edx+edx]
    cmp    eax, 8192
    ja    L29
    .p2align 4,,7
L19:
    mov    BYTE PTR _ZZ4mainE5flags[eax], 0
    add    eax, edx
    cmp    eax, 8192
    jbe    L19
L29:
    inc    ecx
L12:
    inc    edx
    cmp    edx, 8192
    jbe    L20
    dec    ebx
    cmp    ebx, -1
    jne    L21
    push    eax
    push    eax
    push    ecx
    push    OFFSET FLAT:LC0
LCFI3:
    call    _printf
    mov    ebx, DWORD PTR [ebp-4]
    xor    eax, eax
    leave
    ret
LFE1:
    .def    _printf;    .scl    2;    .type    32;    .endef