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

Q>На интерпретаторе (!) ghci под Windows на моей не самой быстрой машине первые 5000 (до 48619) чисел вычислились за 40 секунд, что примерно в 2 раза быстрее, чем на твоей программе .
Ну если тебе надо 5000 то...

number = 2 x = 1 count = 1 time = 6.56336e-06
number = 3 x = 2 count = 2 time = 0.00123109
number = 5 x = 3 count = 3 time = 0.00220563
number = 7 x = 5 count = 4 time = 0.00318859
number = 11 x = 8 count = 5 time = 0.00425005
number = 17 x = 13 count = 7 time = 0.00521524
number = 23 x = 21 count = 9 time = 0.0062029
number = 37 x = 34 count = 12 time = 0.00726603
number = 59 x = 55 count = 17 time = 0.00827418
number = 97 x = 89 count = 25 time = 0.00942301
number = 149 x = 144 count = 35 time = 0.0104404
number = 239 x = 233 count = 52 time = 0.0114785
number = 379 x = 377 count = 75 time = 0.0132433
number = 613 x = 610 count = 112 time = 0.0142888
number = 991 x = 987 count = 167 time = 0.0155076
number = 1601 x = 1597 count = 252 time = 0.0165676
number = 2591 x = 2584 count = 377 time = 0.0177834
number = 4201 x = 4181 count = 575 time = 0.0188863
number = 6779 x = 6765 count = 872 time = 0.0201199
number = 10949 x = 10946 count = 1330 time = 0.021233
number = 17713 x = 17711 count = 2034 time = 0.0225363
number = 28661 x = 28657 count = 3122 time = 0.0237418
number = 46381 x = 46368 count = 4795 time = 0.0249562
total = 5136 time = 0.0262307

Подавляющие время занял вывод.
Q>Знаю, знаю. Твоя программа сразу знала верхний предел и поэтому вычеркивала числа сразу до него . Но что же делать, я то имел ввиду ленивые вычисления, и моя программа могла бы быть написана более эффективно, если бы был задан верхний предел. Т.е. задачи решаются разные. Для сравнения нужна программа, которая заранее не знает сколько от нее потребуют простых чисел.
легко

//Это ограничительная константа(твоя программа раньше сдохнет.)
//На 64х битных платформах ее можно со спкойной совестью еще поднять.
//Но у меня 32х битная машина :(
size_t const max_number=2*1024*1024*1000;
//Этой константой можно играться для тонкой настройки производительности алгоритма
size_t const buf_count=4*1024*1024;
size_t const buf_size=buf_count/CHAR_BIT;

struct prime_numbers
{
    size_t cur_number;
    size_t state;
    size_t offset;
    size_t next_offset;
    std::vector<byte> buf;
    std::vector<size_t> numbers;

    prime_numbers()
        :state(8)
        ,offset(0)
        ,next_offset(buf_count)
        ,buf(buf_size+100)
    {
        numbers.reserve(2*1024*1024);
    }
    void set_bit(size_t n)
    {
        n-=offset;
        size_t pos=n/CHAR_BIT;
        size_t ofs=n%CHAR_BIT;
        buf[pos]|=1<<ofs;
    }
    bool get_bit(size_t n)
    {
        if(n>=next_offset)
        {
            offset=next_offset;
            next_offset+=buf_count;
            std::fill(buf.begin(), buf.end(), 0);
            //вычеркивать начинаем с 7 ибо числа кратные 2, 3, 5 нам всеравно не попадутся :))
            for(size_t i=3, c=numbers.size();i<c;++i)
                remove_number(numbers[i]);
        }
        n-=offset;
        size_t pos=n/CHAR_BIT;
        size_t ofs=n%CHAR_BIT;
        return buf[pos]&(1<<ofs);
    }
    void new_number(size_t i)
    {
        numbers.push_back(i);
        remove_number(i);
    }
    void remove_number(size_t i)
    {
        for(size_t n=(offset/i+1)*i;n<next_offset;n+=i)
            set_bit(n);
    }
    size_t get_next()
    {
        size_t i=cur_number;
        switch(state)
        {
            case  8:    new_number(2);    state= 9;    return 2;
            case  9:    new_number(3);    state=10;    return 3;
            case 10:    new_number(5);    state=11;    return 5;
            case 11:    i=1;
            case 0:
            for(;i<max_number;)
            {
                    i+=6;    if(!get_bit(i))    {new_number(i);    state=1;    return cur_number=i;}
            case 1:    i+=4;    if(!get_bit(i))    {new_number(i);    state=2;    return cur_number=i;}
            case 2:    i+=2;    if(!get_bit(i))    {new_number(i);    state=3;    return cur_number=i;}
            case 3:    i+=4;    if(!get_bit(i))    {new_number(i);    state=4;    return cur_number=i;}
            case 4:    i+=2;    if(!get_bit(i))    {new_number(i);    state=5;    return cur_number=i;}
            case 5:    i+=4;    if(!get_bit(i))    {new_number(i);    state=6;    return cur_number=i;}
            case 6:    i+=6;    if(!get_bit(i))    {new_number(i);    state=7;    return cur_number=i;}
            case 7:    i+=2;    if(!get_bit(i))    {new_number(i);    state=0;    return cur_number=i;}
            }
            state=12;
            case 12:;
        }
        return -1;
    }
};
#include "1.h"
int main()
{
    prime_numbers numbers;
    timer.reset();
    for(;;)
    {
        size_t n=numbers.get_next();
        if(n==-1)
            break;
        on_prime_number_print(n);
    }
    std::cout<<"total = "<<count<<" time = "<<timer.time()<<std::endl;
    return 0;
}

эта падла еще и работать быстрее стала.
Хотя на придельной дистанции получилось медленнее надо будет попробевать ее пооптимизировать

number = 2 x = 1 count = 1 time = 0.011247
number = 3 x = 2 count = 2 time = 0.0224944
number = 5 x = 4 count = 3 time = 0.0287227
number = 11 x = 8 count = 5 time = 0.0357256
number = 17 x = 16 count = 7 time = 0.0404335
number = 37 x = 32 count = 12 time = 0.0475099
number = 67 x = 64 count = 19 time = 0.0526
number = 131 x = 128 count = 32 time = 0.059383
number = 257 x = 256 count = 55 time = 0.0659315
number = 521 x = 512 count = 98 time = 0.0716429
number = 1031 x = 1024 count = 173 time = 0.0795682
number = 2053 x = 2048 count = 310 time = 0.0849316
number = 4099 x = 4096 count = 565 time = 0.0922635
number = 8209 x = 8192 count = 1029 time = 0.0975916
number = 16411 x = 16384 count = 1901 time = 0.103196
number = 32771 x = 32768 count = 3513 time = 0.113651
number = 65537 x = 65536 count = 6543 time = 0.124821
number = 131101 x = 131072 count = 12252 time = 0.133369
number = 262147 x = 262144 count = 23001 time = 0.140619
number = 524309 x = 524288 count = 43391 time = 0.146233
number = 1048583 x = 1048576 count = 82026 time = 0.153858
number = 2097169 x = 2097152 count = 155612 time = 0.164312
number = 4194319 x = 4194304 count = 295948 time = 0.258359
number = 8388617 x = 8388608 count = 564164 time = 0.376738
number = 16777259 x = 16777216 count = 1077872 time = 0.637997
number = 33554467 x = 33554432 count = 2063690 time = 1.21231
number = 67108879 x = 67108864 count = 3957810 time = 2.65548
number = 134217757 x = 134217728 count = 7603554 time = 6.5156
number = 268435459 x = 268435456 count = 14630844 time = 17.9281
number = 536870923 x = 536870912 count = 28192751 time = 54.6199
number = 1073741827 x = 1073741824 count = 54400029 time = 180.671
total = 102754101 time = 608.485

Q>Кстати, OCaml, думаю, вообще не проиграл бы в производительности, поскольку на него твою программу можно перенести 1 в 1.
Если писать императивно. Кстати напиши. И сравним производительность