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

G>Чудеса оптимизации.
хъ
G>15.67 секунд, 98 мегов памяти. Вот теперь все нормально.
Гы!
G>У тебя на компе будет ~14.16 секунд. Против 8.66 твоих. Теперь ты примерно в 1.6 раз быстрее.
У меня Execution: 13.85 Garbage collection: 0.00 Total: 13.85
G>А разница в расходе памяти объясняется только отсутствием упаковки bool массивов.
Я тебе больше скажу... Этим же объясняется и разрыв в производительности... См ниже...
G>Ну как, сделаешь версию на char?
Сделал... Блин я чуть со стула не упал... 13.5022

int main()
{
    timer_t timer;
    unsigned size=100000000;
    std::vector<char> is_prime(size, true);    //помечаем все числа как простые
    for(unsigned i=2;i<size;++i)            //ищем очередное не вычеркнутое число
        if(is_prime[i])                        //i очередное простое число
            for(unsigned n=i+i;n<size;n+=i)    //вычеркиваем все числа кратные данному числу
                is_prime[n]=false;
    std::cout<<timer.time()<<"\n";
}

Хотя код получился на много меньше и с виду быстрее...

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

    lea    edx, DWORD PTR $T72542[esp+72]
    push    edx
    push    100000000                ; 05f5e100H
    lea    ecx, DWORD PTR _is_prime$[esp+80]
    mov    BYTE PTR $T72542[esp+80], 1
    call    ?_Construct_n@?$vector@DV?$allocator@D@std@@@std@@QAEXIABD@Z ; std::vector<char,std::allocator<char> >::_Construct_n

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

    mov    esi, DWORD PTR _is_prime$[esp+76]
    mov    DWORD PTR __$EHRec$[esp+80], 0
    mov    ecx, 2
    npad    5
$L64503:

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

    cmp    BYTE PTR [esi+ecx], 0
    je    SHORT $L64504

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

    cmp    ecx, 50000000                ; 02faf080H
    lea    eax, DWORD PTR [ecx+ecx]
    jae    SHORT $L64504
$L64508:

; 39   :                 is_prime[n]=false;

    mov    BYTE PTR [esi+eax], 0
    add    eax, ecx
    cmp    eax, 100000000                ; 05f5e100H
    jb    SHORT $L64508
$L64504:

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

    inc    ecx
    cmp    ecx, 100000000                ; 05f5e100H
    jb    SHORT $L64503

Но оказывается узкое место ПАМЯТЬ...
Теперь понятно почему ручная работа с битами практически не сказалась на производительности...