Факторизация - разложение на множители.

[alexu007]

Ускоренный вариант, использующий свойство простых чисел (6*n плюс-минус 1). Максимальное число 2⁶⁴. Время вычисления максимальных значений (на моём компе) около 10 сек.

Код:

#ifndef WIDGET_H
#define WIDGET_H

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


#define FUNC_FIND_D   while(!(n % x))\
                      {\
                          sum *= x;\
                          str += QString::number(x) + "  ";\
                          n /= x;\
                          if(n % x) str += "\n";\
                       }


QT_BEGIN_NAMESPACE
namespace Ui { class Widget; }
QT_END_NAMESPACE

class Widget : public QWidget
{
    Q_OBJECT

public:
    Widget(QWidget *parent = nullptr);
    ~Widget();

private:
    Ui::Widget *ui;

    QTime m_time;
    quint64 t_begin;

public slots:
    void press_pbtn_01();
};
#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->pbtn_01,SIGNAL(clicked()),this,SLOT(press_pbtn_01()));
}





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




// start
void Widget::press_pbtn_01()
{
    QString str = ui->lineEdit->text();


    quint64 n, x;
    quint64 sum = 1;
    quint64 N = str.toULongLong();

    quint64 qn = sqrt(N)/6 + 2;

    ui->textEdit->clear();
    ui->label_01->clear();
    QApplication::processEvents();

    // проверка на переполнение
    if((N < 1) || (N > 18446744073709551615uL))
    {
        ui->textEdit->setText("Incorrect (low, large) digit");
        return;
    }

    str = "1\n";
    n = N;

    // начало отсчёта времени выполнения
    m_time.start();

    x = 2;
    FUNC_FIND_D

    x = 3;
    FUNC_FIND_D

    for(quint64 i = 1; i < qn; i++)
    {
        x = i * 6 - 1;
        FUNC_FIND_D

        x++;
        x++;
        FUNC_FIND_D
    }

    n = N / sum;
    if(n > 1) str += QString::number(n);


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

    ui->textEdit->append(str);
    ui->label_01->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));
}

[Day]

свойство простых чисел (6*n плюс-минус 1).

Можно взять вместо Шестерки Праймориал побольше. 30, 210 и так далее. А 30 дает возможность построить очень компактное решето

[alexu007]

Я выкладывал ранее код проверки на простоту с использованием свойств 30-ки:

Код:

int Prime(quint64 a)
{
     quint64 i1, i2, i3, i4, i5, i6, i7, i8, bound;

     if (a == 0 || a == 1) return 0;

     if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17
             || a == 19 || a == 23 || a == 29) return 1;

     if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 ||
         a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
         return 0;

     bound = sqrt((double)a);

     i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;

     while(i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
     {
         i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
     }

     if( i8 <= bound ||
        (i1 <= bound && a % i1 == 0) ||
        (i2 <= bound && a % i2 == 0) ||
        (i3 <= bound && a % i3 == 0) ||
        (i4 <= bound && a % i4 == 0) ||
        (i5 <= bound && a % i5 == 0) ||
        (i6 <= bound && a % i6 == 0) ||
        (i7 <= bound && a % i7 == 0) )  return 0;

     return 1;
}

Он работает на 2 секунды быстрее, т.е. находит максимальное простое число за 10 сек, мой код - за 12 сек (на моём компе, ессно...). Не такой уж и значительный выигрыш.

С решетом я экспериментировал. О результатах сообщу позднее.