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

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

Показов 46322 Комментарии 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 (bedvit@mail.ru)
#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 (bedvit@mail.ru)\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

Новые блоги и статьи Все статьи Все блоги /
Циклы for в Python py-thonny 17.03.2025 Существует множество ситуаций, когда нам нужно выполнить одно и то же действие несколько раз. Цикл for в Python — настоящий рабочий конь для большинства программистов. Если вам нужно пройтись по всем. . .	Предсказание ветвлений - путь к высокопроизводительному C++ NullReferenced 17.03.2025 В высокопроизводительном программировании на C++ каждый такт процессора на счету. Когда речь заходит о разработке систем с низкой задержкой — будь то высокочастотная торговля, обработка потоковых. . .	Паттерн CQRS в C# UnmanagedCoder 17.03.2025 Создание сложных корпоративных приложений часто требует нестандартных подходов к архитектуре. Один из таких подходов — паттерн CQRS (Command Query Responsibility Segregation), предлагающий простую,. . .	Паттерн Цепочка ответственности в C# UnmanagedCoder 17.03.2025 Цепочка ответственности — это поведенческий паттерн проектирования, который позволяет передавать запросы последовательно по цепочке потенциальных обработчиков, пока один из них не обработает запрос. . . .	Создаем микросервисы с NestJS, TCP и Typescript run.dev 17.03.2025 NestJS — фреймворк, который значительно упрощает создание серверных приложений на Node. js. Его прелесть в том, что он комбинирует концепции ООП, функционального программирования и предлагает. . .
Гексагональная архитектура со Spring Boot Javaican 17.03.2025 Если вы когда-нибудь сталкивались с ситуацией, когда внесение простых изменений в базу данных или пользовательский интерфейс заставляло вас переписывать весь код, то вы точно оцените элегантность. . .	Позиционирование Kafka Consumer и Seek-операции Javaican 17.03.2025 Что же такое Consumer Seek в Kafka? По сути, это API-метод, который позволяет программно указать, с какой позиции (offset) Consumer должен начать или продолжить чтение данных из партиции. Без этого. . .	Python NumPy: Лучшие практики и примеры py-thonny 17.03.2025 NumPy (Numerical Python) — одна из ключевых библиотек для научных вычислений в Python. Она превращает Python из просто удобного языка общего назначения в среду для проведения сложных математических. . .	Java Micronaut в Docker: контейнеризация с Maven и Jib Javaican 16.03.2025 Когда речь заходит о микросервисной архитектуре на Java, фреймворк Micronaut выделяется среди конкурентов. Он создан с учётом особенностей облачных сред и контейнеров, что делает его идеальным. . .	Управление зависимостями в Java: Сравнение Spring, Guice и Dagger 2 Javaican 16.03.2025 Инъекция зависимостей (Dependency Injection, DI) — один из фундаментальных паттернов проектирования, который радикально меняет подход к созданию гибких и тестируемых Java-приложений. Суть этого. . .

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

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

Архив
< Март 2025
Вс	Пн	Вт	Ср	Чт	Пт	Сб
23	24	25	26	27	28	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	1	2	3	4	5