Форум программистов, компьютерный форум, киберфорум
bedvit
Форум программистов и сисадминов Киберфорум > Блоги > bedvit
Войти
Регистрация
Восстановить пароль
Карта форума Блоги Сообщество Поиск Заказать работу  
Рейтинг: 3.40. Голосов: 5.

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

Запись от bedvit размещена 18.05.2017 в 18:12
Обновил(-а) bedvit 30.05.2019 в 11:11
Столкнувшись с данной тематикой, ранее как-то спокойно проходящей мимо меня, решил немного посвятить время и разобраться на уровне обычного человека (!= Перельман Г.Я.)
Итак не открою тайны, что достаточно большие числа долго раскладываются на простые большие множители, на чем основывается, к примеру алгоритм 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
Вложения
Тип файла: rar C++Dividers(последняя_версия_продукта).rar (302.6 Кб, 614 просмотров)
Размещено в Без категории
Показов 45335 Комментарии 7
« Оптимизация производительности C#.NET (Алгоритм, Многопоточность, Debug, Release, .Net Core, .Net Native, С++)     Главная страница     Хранение файлов и файловый менеджер в файле(листе) Excel, Бинарное хранение данных в CustomProperty листа Excel - VBA »
Всего комментариев 7
Комментарии
  1. Старый комментарий
    Аватар для Байт
    Цитата:
    делить уже остаток от деления N на предыдущий найденный простой делитель
    Я правильно понимаю, что здесь небольшая неточность? Вы наверное, хотели сказать - результат от деления (частное)?
    Цитата:
    30k+1, 30k+7, ...
    Кстати, тридцадка чудо как хороша для компактного представления списка простых. Остатков-то всего 8 = числу битов в байте.
    А вот 210 уже ничего в этом смысле не дает. Конечно, при достаточном количестве процессоров можно и по ним раскидать...Но 30 является неким оптиумом...
    Запись от Байт размещена 23.01.2018 в 18:44 Байт вне форума
  2. Старый комментарий
    Аватар для bedvit
    Верное замечание, в математическом понимании - это результат от деления (частное). Ведь здесь все деления - целочисленные, остатков от деления нет. Видимо тогда писал в логике остаток данных в результате вычисления итерации, что по сути "частное".
    "Остатков-то всего 8 = числу битов в байте" - как можно использовать?
    30 - это удобно, согласен, а еще 8 - это число моих процессоров (логических), что то же удобно (параллелить)!
    Запись от bedvit размещена 23.01.2018 в 19:43 bedvit вне форума
  3. Старый комментарий
    Аватар для Байт
    Цитата:
    "Остатков-то всего 8 = числу битов в байте" - как можно использовать?
    просто решето компактное строится. На каждую тридцатку чисел - 1 байт. Битики отвечают за +1,+7, +11,+13,+17,+19,+23,+29
    Где-то был и код даже. Если интересно - по сусекам поищу...
    Запись от Байт размещена 23.01.2018 в 20:17 Байт вне форума
  4. Старый комментарий
    Аватар для bedvit
    В данном алгоритме решето не строится, простое число вычисляется в каждом из 8 потоков по своей прогрессии, если решение не найдено и оно нужно (по возрастанию). Вернее, скажем так, оно строится в процессе разложения числа, но запоминается последний элемент. Предыдущие уже не нужны, ведь на них уже было деление или они не являлись делителем. Но ваш код, я бы посмотрел, если не далеко завалился
    Запись от bedvit размещена 23.01.2018 в 20:47 bedvit вне форума
  5. Старый комментарий
    Аватар для Байт
    Вот нашел, довольно быстро. Собственно, это уплотненное решето, и ничего больше. Пригодится вам - хорошо. Нет - тоже не страшно
    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 Байт вне форума
  6. Старый комментарий
    Аватар для bedvit
    Спасибо! Старый, добрый Си...
    Запись от bedvit размещена 23.01.2018 в 21:37 bedvit вне форума
  7. Старый комментарий
    ...проверку на ввод 0 бы ещё добавить)
    Запись от КиберСталкер21 размещена 10.04.2023 в 17:33 КиберСталкер21 вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru