Здравствуйте, Gaperton, Вы писали:

G>Я тоже хочу именно этого. Приступим. Вот дословный перевод твоего алгоритма на Clean.
Так так... Деструктивное изменение массива... те от функционального языка остался только синтаксис...

G>Давай мы все-таки не будем меряться скоростью свопа и количеством оперативки, хорошо?
А у тебя что меньше ста дватцати метров?
G>Твоя прога выделяет минимум гигабайт памяти — у меня столько нет.
Не она выделяет примеро 120 метров... ибо std::vector<bool> это массив битов по стандарту...
G>Так что давай меряться на 100 миллионах, ок?
Да мне пофигу.
G>ломает меня с вводом-выводом разбираться. Поэтому просто вернем значение ячейки №31.
Ой как все запущено то...
G>Как видишь, получилось короче — в основном заслуга array и list comprehensions.
Да я бы не сказал.

    unsigned size=1000000000;
    std::vector<bool> is_prime(size, true);//помечаем все числа как простые
    for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число
        if(is_prime[i])
            for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все числа кратные данному числу
                is_prime[n]=false;

; 6    :     unsigned size=100000000;
; 7    :     std::vector<bool> is_prime(size, true);    //помечаем все числа как простые

    lea    edx, DWORD PTR $T74423[esp+76]
    push    edx
    xor    esi, esi
    push    3125000                    ; 002faf08H
    lea    ecx, DWORD PTR _is_prime$[esp+88]
    mov    DWORD PTR _is_prime$[esp+84], esi
    mov    DWORD PTR $T74423[esp+84], -1
    call    ?_Construct_n@?$vector@IV?$allocator@I@std@@@std@@QAEXIABI@Z ; std::vector<unsigned int,std::allocator<unsigned int> >::_Construct_n
    push    100000000                ; 05f5e100H
    lea    ecx, DWORD PTR _is_prime$[esp+80]
    mov    DWORD PTR __$EHRec$[esp+88], esi
    call    ?_Trim@?$vector@_NV?$allocator@_N@std@@@std@@IAEXI@Z ; std::vector<bool,std::allocator<bool> >::_Trim

; 9    :         if(is_prime[i])                        //i очередное простое число

    mov    ebx, DWORD PTR _is_prime$[esp+84]
    mov    DWORD PTR __$EHRec$[esp+84], 1
    mov    edi, 2
    push    ebp
$L74729:
    xor    eax, eax
    mov    eax, edi
    mov    ecx, eax
    shr    ecx, 5
    and    eax, 31                    ; 0000001fH
    lea    edx, DWORD PTR [ebx+ecx*4]
    mov    ecx, eax
    mov    eax, DWORD PTR [edx]
    mov    esi, 1
    shl    esi, cl
    test    esi, eax
    je    SHORT $L64774

; 10   :             for(unsigned n=i+i;n<size;n+=i)    //вычеркиваем все числа кратные данному числу

    cmp    edi, 50000000                ; 02faf080H
    lea    edx, DWORD PTR [edi+edi]
    jae    SHORT $L64774

; 11   :                 is_prime[n]=false;

    xor    ebp, ebp
$L64833:
    mov    eax, ebp
    add    eax, edx
    mov    esi, eax
    mov    ecx, ebx
    shr    esi, 5
    lea    esi, DWORD PTR [ecx+esi*4]
    and    eax, 31                    ; 0000001fH
    mov    ecx, 1
    mov    DWORD PTR tv359[esp+80], ecx
    mov    ecx, eax
    mov    eax, DWORD PTR tv359[esp+80]
    shl    eax, cl
    mov    ecx, DWORD PTR [esi]
    add    edx, edi
    not    eax
    and    ecx, eax
    cmp    edx, 100000000                ; 05f5e100H
    mov    DWORD PTR [esi], ecx
    jb    SHORT $L64833
$L64774:

; 8    :     for(unsigned i=2;i<size;++i)            //ищем очередное не вычеркнутое число

    inc    edi
    cmp    edi, 100000000                ; 05f5e100H
    jb    SHORT $L74729

G>23.59 секунд на моей системе.
Execution: 21.31 Garbage collection: 0.21 Total: 21.53 и примерно 290 метров памяти.
Моя программа
8.66727 и примерно 12.8 метров памяти.

Хотя если выкинуть std::vector<bool> и работать с битами ручками то получается лучше хотя и не на много

const unsigned bits=CHAR_BIT*sizeof(unsigned);
void set_bit(unsigned n, unsigned* arr)
{
    unsigned pos=n/bits;
    unsigned ofs=n%bits;
    arr[pos]|=1<<ofs;
}
bool get_bit(unsigned n, unsigned* arr)
{
    unsigned pos=n/bits;
    unsigned ofs=n%bits;
    return arr[pos]&(1<<ofs);
}
int main()
{
    timer_t timer;
    unsigned size=100000000;
    std::vector<unsigned> v(size/bits+1);
    unsigned* arr=&v[0];
    for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число
        if(!get_bit(i, arr))//в i очередное простое число
            for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все кратные данному числу
                set_bit(n, arr);
    std::cout<<timer.time()<<"\n";
    return 0;
}

; 65   :     unsigned size=1000000000;
; 66   :     std::vector<unsigned> v(size/bits+1);

    lea    edx, DWORD PTR $T72444[esp+76]
    push    edx
    xor    esi, esi
    push    31250001                ; 01dcd651H
    lea    ecx, DWORD PTR _v$[esp+84]
    mov    DWORD PTR $T72444[esp+84], esi
    call    ?_Construct_n@?$vector@IV?$allocator@I@std@@@std@@QAEXIABI@Z ; std::vector<unsigned int,std::allocator<unsigned int> >::_Construct_n

; 67   :     unsigned* arr=&v[0];
; 68   :     for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число

    mov    edi, DWORD PTR _v$[esp+80]
    mov    DWORD PTR __$EHRec$[esp+84], esi
    mov    esi, 2
    npad    6
$L72548:

; 69   :         if(!get_bit(i, arr))

    mov    ecx, esi
    and    ecx, 31                    ; 0000001fH
    mov    eax, 1
    shl    eax, cl
    mov    ecx, esi
    shr    ecx, 5
    test    eax, DWORD PTR [edi+ecx*4]
    jne    SHORT $L64574

; 70   :         {
; 71   :             //в i очередное простое число
; 72   :             for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все кратные данному числу

    cmp    esi, 500000000                ; 1dcd6500H
    lea    edx, DWORD PTR [esi+esi]
    jae    SHORT $L64574
$L72547:

; 73   :                 set_bit(n, arr);

    mov    ecx, edx
    and    ecx, 31                    ; 0000001fH
    mov    eax, edx
    mov    ebp, 1
    shl    ebp, cl
    shr    eax, 5
    mov    ecx, DWORD PTR [edi+eax*4]
    add    edx, esi
    or    ecx, ebp
    cmp    edx, 1000000000                ; 3b9aca00H
    mov    DWORD PTR [edi+eax*4], ecx
    jb    SHORT $L72547
$L64574:

; 67   :     unsigned* arr=&v[0];
; 68   :     for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число

    inc    esi
    cmp    esi, 1000000000                ; 3b9aca00H
    jb    SHORT $L72548

8.45668


G>Не, у меня в тот раз была асимптотика O(N*sqrt(N)) — я делал отсечку по sqrt. А перебирал с шагом 4-6-4-6-4-6...
Да я не про твою, а про тот тест который лежит тут