Три решета Эрастофена

Вашему вниманию предлагаются три реализации решета Эрастофена: стандартное, без чётных чисел и (предположительно) использующее свойство простых чисел 30*n+.

Первым ожидаемо "сдулось" обычное решето вследствие переполнения памяти. Вторые два доработали до 4,2 млрд. Решето без чётных чисел осилило рекордные 4,5 млрд, решето 30* при этом значении ушло в бесконечный цикл. О времени работы можете судить сами.

Код:

Код:

#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>
#include <math.h>
#include <QTime>

#include <bitset>
using namespace std;


namespace Ui {
class Widget;
}

class Widget : public QWidget
{
    Q_OBJECT
    
public:
    explicit Widget(QWidget *parent = 0);
    ~Widget();
    
private:
    Ui::Widget *ui;

    QTime m_time;

public slots:
    void MyEventHandler1();
    void MyEventHandler2();
    void MyEventHandler3();
};

#endif // WIDGET_H

Код:

#include "widget.h"
#include "ui_widget.h"


Widget::Widget(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::Widget)
{
    ui->setupUi(this);

    QObject::connect(ui->pushBtn_01, SIGNAL(clicked()), this, SLOT(MyEventHandler1()));
    QObject::connect(ui->pushBtn_02, SIGNAL(clicked()), this, SLOT(MyEventHandler2()));
    QObject::connect(ui->pushBtn_03, SIGNAL(clicked()), this, SLOT(MyEventHandler3()));
}



Widget::~Widget()
{
    delete ui;
}




//функция добавляет пробелы в число 12345678 -> 12 345 678
//---------------------------------------------------------------------------
QString fn_SpsToInt(QString str)
{
    int x = str.length() - 3;
    while(x > 0) {str.insert(x, QString(" ")); x -= 3;}

    return str;
}




// обычное решето эрастофена
void Widget::MyEventHandler1()
{
    QString str = ui->lineEdit->text();
    str = str.remove(" ");

    quint64 N = str.toULongLong();
    quint64 M = sqrt(N)+1;

    // с битсетом
    bitset<0x8FFFFFFF> *bbuf = new bitset<0x8FFFFFFF>;
    bbuf->reset();

    quint64 i, j;


    // начало отсчёта времени
    quint64 t_begin = m_time.elapsed();

    // решето
    for(i = 2; i < M; i++)
    {
        if(!bbuf->test(i))
        {
            for(j = i*i; j < N; j+=i) bbuf->set(j, true);
        }
    }


    // подсчет результата
    quint64 cx = 0;
    quint64 summ = 0;

    for(i = 2; i < N; i++)
     {
        if(!bbuf->test(i))
        {
            cx++;
            summ += i;
        }
     }

    // конец отсчёта времени
    qint64 msecs = m_time.elapsed() - t_begin;
    QTime time(0,0,0,0);

    ui->label_01->setText(fn_SpsToInt(QString::number(cx)));
    ui->label_02->setText(fn_SpsToInt(QString::number(summ)));
    ui->label_03->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));

    delete bbuf;
}





// ускоренное решето без чётных чисел
void Widget::MyEventHandler2()
{
    QString str = ui->lineEdit->text();
    str = str.remove(" ");

    quint64 N = str.toULongLong() / 2;
    quint64 M = sqrt(N)+1;

    // с битсетом
    bitset<0x8FFFFFFF> *bbuf = new bitset<0x8FFFFFFF>;
    bbuf->reset();

    quint64 i, j, k;


    // начало отсчёта времени
    quint64 t_begin = m_time.elapsed();

    // решето
    for(i = 0; i < M; i++)
    {
        if(!bbuf->test(i))
        {
            k = (i*2)+3;
            for(j = k*(i+1)+i; j < N; j+=k) bbuf->set(j,true);
        }
    }


    // подсчет результата
    quint64 cx = 1;
    quint64 summ = 2;

    for(i = 0; i < N-1; i++)
    {
        if(!bbuf->test(i))
        {
            k = (i*2 + 3);
            cx++;
            summ += k;
        }
    }

    // конец отсчёта времени
    qint64 msecs = m_time.elapsed() - t_begin;
    QTime time(0,0,0,0);

    ui->label_04->setText(fn_SpsToInt(QString::number(cx)));
    ui->label_05->setText(fn_SpsToInt(QString::number(summ)));
    ui->label_06->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));

    delete bbuf;
}



// решето 30*
void Widget::MyEventHandler3()
{
    QString str = ui->lineEdit->text();
    str = str.remove(" ");

    quint64 N = str.toULongLong();
    quint64 M = sqrt(N);
    quint64 V = N/30 + 1;

    static int Rest[8] = {1, 7, 11, 13, 17, 19, 23, 29};

    quint8 kos;
    quint32 p, i, j;
    quint32 x, d, r, m;

    QByteArray bbuf(0x2fffffff, 0);

    bbuf[0] = 1;


    // начало отсчёта времени
    quint64 t_begin = m_time.elapsed();

    // решето
    for(i = p = 0; p <= M; i++)
    {
        for(j = 0; j < 8; j++)
        {
            if (bbuf[i] & (1 << j)) continue;
            p = 30*i + Rest[j];

            for(x = 7 * p; ;x += 2 * p)
            {
                d = x / 30;
                if (d >= V) break;
                r = x % 30;

                for(m = 0; m < 8; m++) if (r == Rest[m]) break;
                if (m == 8) continue;

                kos = bbuf[d];
                kos |= (1 << m);
                bbuf[d] = kos;
            }
        }
    }


    // подсчет результата
    quint64 cx = 3;
    quint64 summ = 10;

    for(i = 0; i < V; i++)
    {
        for(j = 0; j < 8; j++)
        {
            if (bbuf[i] & (1 << j)) continue;

            x = 30*i + Rest[j];
            if(x > N) break;

            cx++;
            summ += x;
        }
    }

    // конец отсчёта времени
    qint64 msecs = m_time.elapsed() - t_begin;
    QTime time(0,0,0,0);

    ui->label_07->setText(fn_SpsToInt(QString::number(cx)));
    ui->label_08->setText(fn_SpsToInt(QString::number(summ)));
    ui->label_09->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));
}