Быстрый алгоритмы поиска простых/всех делителей натурального числа (в т.ч. факторизация натурального числа)С++

Запись от bedvit размещена 18.05.2017 в 18:12

Показов 46514 Комментарии 7

Метки c++

Столкнувшись с данной тематикой, ранее как-то спокойно проходящей мимо меня, решил немного посвятить время и разобраться на уровне обычного человека (!= Перельман Г.Я.)
Итак не открою тайны, что достаточно большие числа долго раскладываются на простые большие множители, на чем основывается, к примеру алгоритм RSA.(Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел)
Поэтому в данной теме хочу разобрать максимально быстрый алгоритм поиска простых делителей числа, который можно реализовать не профессионалом по математике/программированию, без распределенный вычислений, на обычном ПК.

Итак какие оптимизации сделаны (по порядку внесения в проект):
1.Начиналось все с алгоритма поиска всех делителей - обычным перебором долго, хотя современный ПК позволяет это делать до пределов размера числа 2^64.
2.Ввести верхнюю границу перебора как корень из N (задаваемого числа, для которого ищем делители) - логично, если мы ищем делители.
3.Отказаться от прямого перебора и делить уже остаток от деления N на предыдущий найденный простой делитель, тем самым уменьшая количество итераций и пересчитывая верхнюю границу как корень из N.
4.Расспаралелить процесс расчета (в данном проекте получилось на 8/9 потоков)
5.На самом деле перебирать нужно не все числа, а нужен лишь цикл по простым числам.
Была мысль использовать решето Эратосфена или Решето Аткина.
В итоге реализована оптимизация wheel factorization, если кратко - все простые числа, кроме 2, 3 и 5, лежат в одной из восьми следующих арифметических прогрессий: 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 и 30k+29.
Для каждого потока своя прогрессия.
6.Максимальный размер числа на данном этапе == машинному слову, т.е. 2^64-1
Подключаем библиотеку MPIR is licensed LGPL v3+.
Как подключить (Инструкции по использованию библиотек GMP и MPIR в системе Windows)
7.Внедряем библиотеку в свой проект - размер задаваемого числа теперь зависит только от производительности ПК.
8.Оптимизируем весь проект:
8.1.Проверка N на простое число - MPIR
8.2.Проверка на размер числа (до 2^64-1) - расчет на родном unsigned long long, далее через mpz_class библиотеки MPIR.
8.3.Факторизация числа (разложение на простые делители)
Элементарно решается данным кодом поменяв строку 1 на строку 2 в коде:

Кликните здесь для просмотра всего текста

C++
1
2
if (oldMn != Mn) std::cout << Mn << std::endl;//меняем на
std::cout << Mn << std::endl;

В проекте морф алгоритма на поиск всех делителей (не только простых).

Сборка х64
Код и .exe:
1. На unsigned long long:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <mpirxx.h>
#include <iostream>
#include <time.h>
#include <vector>
#include <thread>
 
unsigned long long Ostatok;
unsigned long long Ostatok2;
 
void Func(int start)
{
    unsigned long long Ch = (1);
    unsigned long long Mn = 30 * Ch + start;
    unsigned long long oldMn;
 
    while (Mn <= Ostatok2) {
        if (Ostatok%Mn == 0) {
            Ostatok = Ostatok / Mn;
            if (oldMn != Mn) std::cout << Mn << std::endl;
            Ostatok2 = (unsigned long long)sqrt(Ostatok);
            oldMn = Mn;
        }
        else {
            Ch++;
            Mn = 30 * Ch + start;
        }
    }
}
 
int main()
{
    std::string s;
    std::cout << "Enter the numeric for which you want to find Simple dividers, followed by <Enter>:\n";
    std::cin >> Ostatok;//s;
    std::cout << "Result:\n1" << std::endl;
    unsigned int start_time = clock(); // начальное время
    Ostatok2 = (unsigned long long)sqrt(Ostatok);
    unsigned long long Mn = (2);
    unsigned long long oldMn;
 
    while (Mn <= 30) {
        if (Ostatok%Mn == 0) {
            Ostatok = Ostatok / Mn;
            if (oldMn != Mn) std::cout << Mn << std::endl;
            Ostatok2 = (unsigned long long)sqrt(Ostatok);
            oldMn = Mn;
        }
        else { Mn++; }
    }
 
    std::vector<std::thread> thr(8);
    int arr[] = { 0,1,7,11, 13, 17, 19, 23, 29 };
    for (int i = 1; i <= 8; i++) thr[i - 1] = std::thread(Func, arr[i]);
    for (int i = 1; i <= 8; i++) thr[i - 1].join();
    if (Ostatok > 1) std::cout << Ostatok << std::endl;
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    printf("\nTime, sec (min): %f (%f) \n", search_time / 1000.0, search_time / 60000.0);
    system("pause");
    return 0;
}

Через mpz_class библиотек MPIR:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <mpirxx.h>
#include <iostream>
#include <time.h>
#include <vector>
#include <thread>
 
unsigned long long Ostatok;
unsigned long long Ostatok2;
mpz_class mpz_Ostatok;
mpz_class mpz_Ostatok2;
 
void Func(int start)
{
    unsigned long long Ch=(1);
    unsigned long long Mn = 30 * Ch + start;
    unsigned long long oldMn;
 
    while (Mn <= Ostatok2) {
        if (Ostatok%Mn == 0) {
            Ostatok = Ostatok / Mn;
            if (oldMn != Mn) std::cout << Mn << std::endl;
            Ostatok2 = (unsigned long long)sqrt(Ostatok);
            oldMn = Mn;
        }
        else{
            Ch++;
            Mn = 30 * Ch + start;
        }
    }
}
void Func2(int start)
{
    mpz_class Ch = (1);
    mpz_class Mn = 30 * Ch + start;
    mpz_class oldMn;
 
    while (Mn <= mpz_Ostatok2) {
        if (mpz_Ostatok%Mn == 0) {
            mpz_Ostatok = mpz_Ostatok / Mn;
            if (oldMn != Mn) std::cout << Mn << std::endl;
            mpz_Ostatok2 = sqrt(mpz_Ostatok);
            oldMn = Mn;
        }
        else {
            Ch++;
            Mn = 30 * Ch + start;
        }
    }
}
int main()
{
    bool mpz_Start;
    mpz_class oldMn;
    std::string s;
    std::cout << "Enter the numeric for which you want to find Simple dividers, followed by <Enter>:\n";
    std::cin >> s;//Ostatok;//s;
    std::cout << "Result:\n1" << std::endl;
    unsigned int start_time = clock(); // начальное время
    mpz_Ostatok = s;
    if (mpz_probab_prime_p(mpz_Ostatok.get_mpz_t(), 100) == 0) {
 
        std::vector<std::thread> thr(8);
        int arr[] = { 0,1,7,11, 13, 17, 19, 23, 29 };
 
        if (mpz_Ostatok > 18446744073709551615) {
            mpz_Ostatok2 = sqrt(mpz_Ostatok);
            mpz_class Mn = (2);
            mpz_class oldMn;
            while (Mn <= 30) {
                if (mpz_Ostatok%Mn == 0) {
                    mpz_Ostatok = mpz_Ostatok / Mn;
                    if (oldMn != Mn) std::cout << Mn << std::endl;
                    mpz_Ostatok2 =sqrt(mpz_Ostatok);
                    oldMn = Mn;
                }
                else { Mn++; }
            }
            for (int i = 1; i <= 8; i++) thr[i - 1] = std::thread(Func2, arr[i]);
            for (int i = 1; i <= 8; i++) thr[i - 1].join();
            if (mpz_Ostatok > 1) std::cout << mpz_Ostatok << std::endl;
        }
        else {
            Ostatok = mpz_Ostatok.get_ui();
            Ostatok2 = (unsigned long long)sqrt(Ostatok);
            unsigned long long Mn = (2);
            unsigned long long oldMn;
            while (Mn <= 30) {
                if (Ostatok%Mn == 0) {
                    Ostatok = Ostatok / Mn;
                    if (oldMn != Mn) std::cout << Mn << std::endl;
                    Ostatok2 = (unsigned long long)sqrt(Ostatok);
                    oldMn = Mn;
                }
                else { Mn++; }
            }
            for (int i = 1; i <= 8; i++) thr[i - 1] = std::thread(Func, arr[i]);
            for (int i = 1; i <= 8; i++) thr[i - 1].join();
            if (Ostatok > 1) std::cout << Ostatok << std::endl;
        }
    }
    else { std::cout << s << std::endl; }
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    printf("\nTime, sec (min): %f (%f) \n", search_time / 1000.0, search_time / 60000.0);
    system("pause");
    return 0;
}

23/05/2017 Продолжение...

9.Итак добавив мультипоточное вычисление с общими глобальными переменными, нужно позаботится о синхронизации потоков и потокобезопасности этих переменных. Есть разные инструменты - Критические секции, Взаимоисключения(Объекты-взаимоисключения (мьютексы, mutex - от MUTual EXclusion)), События, Семафоры, использование атомарных переменных С++ и функций и т.д.
Я остановился на Критических секциях.
10.Далее добавляем алгоритмы расчёта всех делителей числа, факторизации числа (немного модефицировав текущий алгоритм).
11.Добавляем код на увеличение размера консоли (10 000 строк - что бы влезали все делители для больших чисел), добавляем счетчик решений, и продукт готов.

ФУНКЦИОНАЛ:
1.Факторизация числа
2.Поиск простых делителей числа
3.Поиск всех делителей числа

Размер задаваемого числа ограничен лишь производительностью Вашего/моего ПК (к примеру для числа 25-35 десятичных от долей секунды и выше - сильно зависит от количества мелких простых делителей, общего количества простых делителей и других особенностей данного алгоритма разложения числа).

КОД Relese x64

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
// Делители числа
//Created by ©2017, bedvit ([email protected])
#include <mpirxx.h>
#include <iostream>
#include <time.h>
#include <vector>
#include <thread>
#include <Windows.h>
 
CRITICAL_SECTION cs;//критическая секция
unsigned long long Ostatok;
unsigned long long Ostatok2;
unsigned long long oldMn;
unsigned long long ArrRez[3000] = {0,1};
int option;
int Solutions(1);
int y(1);
int y2(1);
mpz_class mpz_Ostatok;
mpz_class mpz_Ostatok2;
mpz_class mpz_oldMn;
mpz_class mpz_ArrRez[100000] = { 0,1 };
 
void Func(int start)
{
    unsigned long long Ch=(1);
    unsigned long long Mn = 30 * Ch + start;
    while (Mn <= Ostatok2) {
        if (Ostatok%Mn == 0) {
        EnterCriticalSection(&cs);//критическая секция
        Ostatok = Ostatok / Mn;
        Ostatok2 = (unsigned long long)sqrt(Ostatok);
            if (option == 3) {
                if (oldMn != Mn) {
                    for (y = 1; y <= Solutions; y++) {
                    ArrRez[Solutions + y] = ArrRez[y] * Mn;
                    std::cout << ArrRez[Solutions + y] << std::endl;
                    }
                Solutions = Solutions + y - 1;
                    }
                else {
                    for (y2 = 1; y2 < y; y2++) {
                    ArrRez[Solutions + y2] = ArrRez[Solutions - y + 1 + y2] * Mn;
                    std::cout << ArrRez[Solutions + y2] << std::endl;
                    }
                Solutions = Solutions + y2 - 1;
                }
            }
            else if (oldMn != Mn || option != 2) { Solutions++; std::cout << Mn << std::endl; } //или
        oldMn = Mn;
        LeaveCriticalSection(&cs);//критическая секция
        }
        else{Ch++;Mn = 30 * Ch + start;}
    }
}
void Func2(int start)
{
    mpz_class mpz_Ch = (1);
    mpz_class mpz_Mn = 30 * mpz_Ch + start;
    while (mpz_Mn <= mpz_Ostatok2) {
        if (mpz_divisible_p(mpz_Ostatok.get_mpz_t(), mpz_Mn.get_mpz_t())==0){mpz_Ch++;mpz_Mn = 30 * mpz_Ch + start;}//проверка на делимость
        else {
        EnterCriticalSection(&cs);//критическая секция
        mpz_Ostatok = mpz_Ostatok / mpz_Mn;
        mpz_Ostatok2 = sqrt(mpz_Ostatok);
            if (option == 3) {//проверка на выбранную опцию
                if (mpz_oldMn != mpz_Mn) {
                    for (y = 1; y <= Solutions; y++) {
                    mpz_ArrRez[Solutions + y] = mpz_ArrRez[y] * mpz_Mn;
                    std::cout << mpz_ArrRez[Solutions + y] << std::endl;
                    }
                Solutions = Solutions + y - 1;
                }
                else {
                    for (y2 = 1; y2 < y; y2++) {
                    mpz_ArrRez[Solutions + y2] = mpz_ArrRez[Solutions - y + 1 + y2] * mpz_Mn;
                    std::cout << mpz_ArrRez[Solutions + y2] << std::endl;
                    }
                Solutions = Solutions + y2 - 1;
                }
            }
            else if (mpz_oldMn != mpz_Mn || option != 2) { Solutions++; std::cout << mpz_Mn << std::endl; } //или
        mpz_oldMn = mpz_Mn;
        LeaveCriticalSection(&cs);//критическая секция
        }
    }
}
int main()
{   InitializeCriticalSection(&cs);
    ////////////////////вывод большого количества строк в консоль
    HANDLE  hout = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD  size;
    size.X = 100;   // кол-во символов на строку
    size.Y = 10010;  // увеличиваем до нужного размера - количества переменных
    SetConsoleScreenBufferSize(hout, size);
    ////////////////////
    std::string s;
    std::cout << "Created by 2017, bedvit ([email protected])\n\nFactorization of a number(factorization)=1\nSearch for prime divisors=2\nSearch for all divisors=3\nSelect a calculation option:= ";
    std::cin >> option;
    std::cout << "Enter the numeric: ";
    std::cin >> s;
    std::cout << "\nResult:\n1" << std::endl;
    unsigned int start_time = clock(); // начальное время
    mpz_Ostatok = s;
    if (mpz_probab_prime_p(mpz_Ostatok.get_mpz_t(), 100) == 0) {
 
        std::vector<std::thread> thr(8);
        int arr[] = { 0,1,7,11, 13, 17, 19, 23, 29 };
 
        if (mpz_Ostatok > 18446744073709551615) {
            mpz_Ostatok2 = sqrt(mpz_Ostatok);
            mpz_class mpz_Mn = (2);
            mpz_class mpz_oldMn;
            while (mpz_Mn <= 30) {
                if (mpz_divisible_p(mpz_Ostatok.get_mpz_t(), mpz_Mn.get_mpz_t()) == 0) { mpz_Mn++;}  //проверка на делимость
                else {
                    mpz_Ostatok = mpz_Ostatok / mpz_Mn;
                    mpz_Ostatok2 = sqrt(mpz_Ostatok);
 
                    if (option == 3) {//проверка на выбранную опцию
                        if (mpz_oldMn != mpz_Mn) {
                            for (y = 1; y <= Solutions; y++) {
                                mpz_ArrRez[Solutions + y] = mpz_ArrRez[y] * mpz_Mn;
                                std::cout << mpz_ArrRez[Solutions + y] << std::endl;
                            }
                            Solutions = Solutions + y - 1;
                        }
                        else {
                            for (y2 = 1; y2 < y; y2++) {
                                mpz_ArrRez[Solutions + y2] = mpz_ArrRez[Solutions - y + 1 + y2] * mpz_Mn;
                                std::cout << mpz_ArrRez[Solutions + y2] << std::endl;
                            }
                            Solutions = Solutions + y2 - 1;
                        }
                    }
                    else if (mpz_oldMn != mpz_Mn || option != 2) { Solutions++; std::cout << mpz_Mn << std::endl; } //или
                    mpz_oldMn = mpz_Mn;
                }
            }
            for (int i = 1; i <= 8; i++) thr[i - 1] = std::thread(Func2, arr[i]);
            for (int i = 1; i <= 8; i++) thr[i - 1].join();
            if (mpz_Ostatok > 1){//проверяем остаток
                if (option == 3) {
                    if (mpz_oldMn != mpz_Ostatok) {
                        for (y = 1; y <= Solutions; y++) {
                            mpz_ArrRez[Solutions + y] = mpz_ArrRez[y] * mpz_Ostatok;
                            std::cout << mpz_ArrRez[Solutions + y] << std::endl;
                        }
                        Solutions = Solutions + y - 1;
                    }
                    else {
                        for (y2 = 1; y2 < y; y2++) {
                            mpz_ArrRez[Solutions + y2] = mpz_ArrRez[Solutions - y + 1 + y2] * mpz_Ostatok;
                            std::cout << mpz_ArrRez[Solutions + y2] << std::endl;
                        }
                        Solutions = Solutions + y2 - 1;
                    }
                }
                else { std::cout << mpz_Ostatok << std::endl; Solutions++; }
            }
        }
        else {
            Ostatok = mpz_Ostatok.get_ui();
            Ostatok2 = (unsigned long long)sqrt(Ostatok);
            unsigned long long Mn = (2);
            unsigned long long oldMn;
            while (Mn <= 30) {
                if (Ostatok%Mn == 0) {//проверка на делимость
                    Ostatok = Ostatok / Mn;
                    Ostatok2 = (unsigned long long)sqrt(Ostatok);
                    
                    if (option == 3) {//проверка на выбранную опцию
                        if (oldMn != Mn) {
                            for (y = 1; y <= Solutions; y++) {
                                ArrRez[Solutions + y] = ArrRez[y] * Mn; 
                                std::cout << ArrRez[Solutions + y] << std::endl; 
                            }
                        Solutions = Solutions + y-1;
                        }
                        else {
                            for (y2 = 1; y2 < y; y2++) { 
                                ArrRez[Solutions + y2] = ArrRez[Solutions - y + 1 + y2] * Mn; 
                                std::cout << ArrRez[Solutions + y2] << std::endl;
                            }
                            Solutions = Solutions + y2 - 1;
                        }
                    }
                    else if (oldMn != Mn || option != 2){Solutions++;std::cout << Mn << std::endl;} //или
                    oldMn = Mn;
                }
                else { Mn++; }
            }
            for (int i = 1; i <= 8; i++) thr[i - 1] = std::thread(Func, arr[i]);
            for (int i = 1; i <= 8; i++) thr[i - 1].join();
            if (Ostatok > 1) {//проверяем остаток
                if (option == 3) {
                    if (oldMn != Ostatok) {
                        for (y = 1; y <= Solutions; y++) {
                            ArrRez[Solutions + y] = ArrRez[y] * Ostatok;
                            std::cout << ArrRez[Solutions + y] << std::endl;
                        }
                        Solutions = Solutions + y - 1;
                    }
                    else {
                        for (y2 = 1; y2 < y; y2++) {
                            ArrRez[Solutions + y2] = ArrRez[Solutions - y + 1 + y2] * Ostatok;
                            std::cout << ArrRez[Solutions + y2] << std::endl;
                        }
                        Solutions = Solutions + y2 - 1;
                    }
                }
                else { std::cout << Ostatok << std::endl; Solutions++; }
            }
        }
    }
    else { std::cout << s << std::endl; Solutions++;}//если число простое
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    printf("\nTime, sec (min): %f (%f) Solutions: %u\n", search_time / 1000.0, search_time / 60000.0, Solutions);
    system("pause");
    return 0;
}

Со всеми оптимизациями алгоритм все равно - Экспоненциальный.
Дальнейшие идеи: реализовать метод рационального/квадратичного решета - субэкспоненциальный алгоритм (на основе идей метода факторизации Ферма).
Что, предполагаю, будет значительно быстрее, чем текущий алгоритм (в особенности на больших числах).
В идеале Общий метод решета числового поля, но он сложнее, много математики, да и реализован он уже на С, серьезными командами
Моя же цель - попробовать создать алгоритм, человеком не профессионалом по математике/программированию, без распределенный вычислений, на обычном ПК.

Замечания и предложения принимаются!
Последняя версия продукта - C++Dividers.exe

Репозиторий на GitHub

Метки c++

Размещено в Без категории

« Оптимизация производительности C#.NET (Алгоритм, Многопоточность, Debug, Release, .Net Core, .Net Native, С++) Главная страница Хранение файлов и файловый менеджер в файле(листе) Excel, Бинарное хранение данных в CustomProperty листа Excel - VBA »

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 7

Комментарии

делить уже остаток от деления N на предыдущий найденный простой делитель

Я правильно понимаю, что здесь небольшая неточность? Вы наверное, хотели сказать - результат от деления (частное)?

30k+1, 30k+7, ...

Кстати, тридцадка чудо как хороша для компактного представления списка простых. Остатков-то всего 8 = числу битов в байте.
А вот 210 уже ничего в этом смысле не дает. Конечно, при достаточном количестве процессоров можно и по ним раскидать...Но 30 является неким оптиумом...

Запись от Байт размещена 23.01.2018 в 18:44 Байт вне форума

Верное замечание, в математическом понимании - это результат от деления (частное). Ведь здесь все деления - целочисленные, остатков от деления нет. Видимо тогда писал в логике остаток данных в результате вычисления итерации, что по сути "частное".
"Остатков-то всего 8 = числу битов в байте" - как можно использовать?

30 - это удобно, согласен, а еще 8 - это число моих процессоров (логических), что то же удобно (параллелить)!

Запись от bedvit размещена 23.01.2018 в 19:43 bedvit на форуме

"Остатков-то всего 8 = числу битов в байте" - как можно использовать?

просто решето компактное строится. На каждую тридцатку чисел - 1 байт. Битики отвечают за +1,+7, +11,+13,+17,+19,+23,+29
Где-то был и код даже. Если интересно - по сусекам поищу...

Запись от Байт размещена 23.01.2018 в 20:17 Байт вне форума

В данном алгоритме решето не строится, простое число вычисляется в каждом из 8 потоков по своей прогрессии, если решение не найдено и оно нужно (по возрастанию). Вернее, скажем так, оно строится в процессе разложения числа, но запоминается последний элемент. Предыдущие уже не нужны, ведь на них уже было деление или они не являлись делителем. Но ваш код, я бы посмотрел, если не далеко завалился

Запись от bedvit размещена 23.01.2018 в 20:47 bedvit на форуме

Вот нашел, довольно быстро. Собственно, это уплотненное решето, и ничего больше. Пригодится вам - хорошо. Нет - тоже не страшно

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdlib.h>
#include <stdio.h>
static int Rest[8] = { 1, 7, 11, 13, 17, 19, 23, 29 };
static unsigned char *A;
static int V; // Объем массива A
#define N 12000  // До какого числа строить решето
 
main()
{ int p, ii, jj;
   V = N/30 + 1;
   A = (unsigned char *)malloc(V);
   A[0] = 1;
   memset(A+1, 0, V-1);
   s = sqrt(N);
   for(ii=p=0; p*p<=N; ii++) {
     for(jj=0; jj<8; jj++) {
       if (A[ii] &(1<<jj)) continue;
       p = 30*ii + Rest[jj]; // Возможно простое
       Jolting(p);  // Проверка
     }
   }
   for(ii=0; ii<V; ii++) {
     for(jj=0; jj<8; jj++) {
       if (A[ii] & (1<<jj)) continue;
       printf ("%d\n", 30*ii + Rest[jj]);
     }
   }
}
// ****************
Jolting(int p)
{ int x, d, r, i;
 
   for(x=7*p; ; x += 2*p) {
     d = x/30;
     if (d >= V) break;
     r = x%30;
     for(i=0; i<8; i++) if (r==Rest[i]) break;
     if (i==8) continue;
     A[d] |= (1<<i);
   }
}
// ****************

Запись от Байт размещена 23.01.2018 в 21:09 Байт вне форума

	Спасибо! Старый, добрый Си...
	Запись от bedvit размещена 23.01.2018 в 21:37

	...проверку на ввод 0 бы ещё добавить)
	Запись от КиберСталкер21 размещена 10.04.2023 в 17:33

Новые блоги и статьи Все статьи Все блоги /
Рисование коллайдеров физического движка Box2D-WASM v3 на Three.js 8Observer8 04.06.2025 Erin Catto (автор Box2D) переписал с нуля Box2D v2 с С++ на Си и появилась версия Box2D v3. Birch-san собрал Box2D v3 в WebAssembly (WASM), чтобы можно было использовать Box2D v3 на JavaScript. В. . .	Worker Threads и многопоточность в Node.js Reangularity 03.06.2025 Если вы когда-нибудь посещали собеседования на позицию Node. js разработчика, почти наверняка слышали заезженную фразу: "Node. js - однопоточная платформа". Звучит как неоспоримый факт, который. . .	Event-Driven CQRS на C# с паттерном Outbox stackOverflow 03.06.2025 В традиционной модели происходит примерно следующее: вы получаете команду, обрабатываете ее, сохраняете результат в базу данных и затем пытаетесь опубликовать событие в брокер сообщений. Но что если. . .	OwenLogic: перенос сетевых переменных в панель Weintek (EasyBuilder Pro) ФедосеевПавел 03.06.2025 ВВЕДЕНИЕ ПЕРЕД ЭКСПЕРИМЕНТАМИ - СОЗДАЙТЕ РЕЗЕРВНЫЕ КОПИИ ПРОЕКТОВ На момент написания статьи (02 июня 2025 г. ) самыми актуальными версиями ПО являются: OwenLogic v. 2. 10. 366 EasyBuilder Pro. . .	Dev-c++5.11 Покорение вершины russiannick 02.06.2025 С утра преследовала одна мысль - вот бы выучить С++. Сказано-сделано. Окончив смену, скачал в интернете бестселлер Дэвиса Dev-C++ для чайников. Книга оказалась интересной и я скачал среду, на примере. . .
Тестирование Pull Request в Kubernetes с GitHub Actions и GKE Mr. Docker 02.06.2025 Мы все знаем, что тестирование на локальной машине или в изолированном CI-окружении — это не совсем то же самое, что тестирование в реальном кластере Kubernetes. Контекстно-зависимые ошибки, проблемы. . .	Оптимизация CMake для ускорения сборки bytestream 02.06.2025 Вы когда-нибудь ловили себя на мысле, что пока ваш проект компилируется, можно успеть сварить кофе, прочитать главу книги или даже сбегать в соседний офис? Если да, то добро пожаловать в клуб. . .	JS String.prototype.localeCompare() mr_dramm 02.06.2025 скопировано из этой темы чтобы не потерялось. localeCompare без указания локали для сравнения строк под капотом использует Intl. Collator , который работает согласно Unicode Collation Algorithm. . .	Облако проектов russiannick 01.06.2025 Слава Джа, написал прогу для компиляции. Значит написал компилятор? Обьем кода 300+ строк. Язык-яву. Вводим данные, заполняем поля, тычем радиобаттоны. И по итогу в поле результат получам листинг. . .	Rust и квантовые вычисления: интеграция с Q# и Qiskit golander 01.06.2025 Мир квантовых вычислений традиционно оставался закрытым клубом для высокоуровневых языков типа Python и специализированных DSL вроде Q#. Однако в последние годы Rust начал тихую революцию в этой. . .

Сообщение форума

Отменить изменения