Форум программистов, компьютерный форум CyberForum.ru

Эффективный алгоритм поиска простых чисел на С++ - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 11:41     Эффективный алгоритм поиска простых чисел на С++ #1
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 1 и на само себя, сложное число-которое делится на 1 и на само себя и на какое-то еще число, 5 -простое число, 10-сложное число.
P.S. Вот программа:
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
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
 int simple (int x,int i=1)
{
    int fn;
    for(i=1;i<=x;i++)
    {
        if(i!=1||i!=x)
        {
            if(!(x%i))
            {
                fn=0;
                return fn;
            }
        }
    }
    fn=1;
    return fn;
}
int main()
{
    //ifstream cin("input.txt");
    long int x,i=1;
    cin>>x;
    if(simple(x,i)==0)
    {
        cout<<"composite";
        return 0;
    }
    if(simple(x,i)==1)
    {
        cout<<"prime";
            return 0;
    }
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 23:06     Эффективный алгоритм поиска простых чисел на С++ #41
-=ЮрА=-,Ваша последняя программа по-прежнему не работает, число 1244042141 не простое, а она говорит, что простое. 1244042141 делится на 181
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 06:46     Эффективный алгоритм поиска простых чисел на С++ #42
Мой алгоритм работает,до ИНТ_МАХ. Хорошо через пару часов еще немного доработав получу универсальный код,ты лучше свой код доработай по тем замечаниям которые даны выше.Поверь я доведу до момента когда ответишь за свои слова, держись малыш)))
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 08:42     Эффективный алгоритм поиска простых чисел на С++ #43
Позволю себе поучаствовать в этом безобразии, т.к. делать нечего.
-=ЮрА=- ваша последняя программа ( та, которая с этим циклом
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
C++
1
for(i = 9 + 2; i <= 100 && bSimple; i += 2)
) способна искать простые числа не больше 10000 (1002).

Делая так,
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
C++
1
isSimple(9999999900000001)
вы хитрите. вы проверяете только делители < 100. этого недостаточно, чтобы доказать простоту того числа.

Вообще, во всех ваших программмах идет последовательный перебор нечетных делителей, а это сложность O(n) для каждого проверяемого числа. Это крайне неэффективно.

PS: -=ЮрА=-, зря вы так про справочники говорите, они помогают сократить время на написание программ, избегать глупых ошибок, неверных и неэффективных (в вашем случае) алгоритмов.
на основе вашей неприязни к справочникам могу предположить, что и библиотеками готовых алгоритмов вы не пользуетесь, и каждый раз всё пишете сначала. Мартышкин труд.
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 09:49     Эффективный алгоритм поиска простых чисел на С++ #44
Цитата Сообщение от ya_noob Посмотреть сообщение
вы хитрите. вы проверяете только делители < 100. этого недостаточно, чтобы доказать простоту того числа.
- я не хитрю я проверяю делители до 2^7 видимо стоит попробовать до 2^8 если бы кто-то в частности и вы

ya_noob, разбирались в математике то увидили бы что пробор от 2 до 11 позволяет рассматривать делители уже в интервале N/10 при этом не следует рассматривать все N/10 делителей, достаточно прогнать до половины разрядов N/10 (т.е до чисел квадрат которых даст порядок рассматриваемого числа) При этом надо ещё посмотреть а не лежат ли все элементарные делителе скажем в пределах 2^8. Я уже отметил до INT_MAX мой алгоритм весьма и весьма эффективен (это воочию показано на числе операций)
Цитата Сообщение от ya_noob Посмотреть сообщение
Вообще, во всех ваших программмах идет тупой последовательный перебор нечетных делителей, а это сложность O(n) для каждого проверяемого числа. Это крайне неэффективно.
- вот именно что если делители лежат до 2 в 8-й лучше просто их пробрать и секономить на итерациях (ведь чисел у которых делители 181 как на пост выше не так уж и много), т.е где то в 90% случаев совершив 5-10 итерайций я уже найду составное число, в то время как просев дает всегда 84 итерации на каждое число

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от ya_noob Посмотреть сообщение
Позволю себе поучаствовать в этом безобразии, т.к. делать нечего.
- лучше займись своими делами

-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 10:35     Эффективный алгоритм поиска простых чисел на С++ #45
Ternsip, ты ещё здесь?
Мы до сих пор разбирали мой алгоритм, верней то что на числах за INT_MAX он ещё не 100% точен, так вот давай лучше займёмся твоим(тебе даже за него + поставил ТС наивно полагая что ты действительно прав). Так вот давай поглядим что выдаст твой алгоритм на числе 2047 (делитель 23) и числе (3277 делитель 29) http://codepad.org/CMneLlht
Заметь по ссілке компипаст твоего кода (никаких моих ремарок)
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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
 
using namespace std;
 
// big numbers
 
long mulmod(long a, long b, long MOD){
    if (b == 0) return 0;
    long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long a, long n) {
    long d = 1;
    long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < pow(2.0, i)) continue;
        long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long n, long tries) {
    for(int it = 0; it < tries; it++) {
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
// low numbers
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
bool witnessLow(int a, int n) {
    int d = 1;
    int b = n - 1;
    for(int i = 31; i >= 0; i--) {
        if(b < (1 << i)) continue;
        int x = d;
        d = (long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) return true;
        if((b >> i) & 1) d = (long(d) * a) % n;
    }
    return (d != 1);
}
 
bool MillerRabinLow(int n) {
      if(n == 2) return true;
    if(witnessLow(2, n)) return false;
    return true;
}
 
bool test(long c){
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
        int arr[] = {2047, 3277};
 
    for(int i = 0; i < 2; i++)
    {
        cout<<arr[i]<<" - ";
        if(test(arr[i]))
            cout<<"SIMPLE"<<endl;
        else
            cout<<"NOT SIMPLE"<<endl;
    }
    return 0; 
}
Т.е уже 2 левых числа даже в первых 5-ти сотнях...
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 10:50     Эффективный алгоритм поиска простых чисел на С++ #46
-=ЮрА=-, повысьте точность if(witnessLow(2, n)) return false; вместо 2-ки в функции MillerRabinLow поставьте 10
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 11:05     Эффективный алгоритм поиска простых чисел на С++ #47
Ternsip, я не хочу ничего повышать, я также мог сказать повысь точность пробора написав вместо 100 256, твой код уже лажает в первых 500 числах, если я повышу точность в твоём коде то в столько же раз упадёт его производительность. Разговор шёл о том что я якобы толкаю туфту юзерам, так вот туфту впарил ты бедолаге ТС.

Добавлено через 6 минут

Не по теме:

Цитата Сообщение от Ternsip Посмотреть сообщение
if(witnessLow(2, n)) return false; вместо 2-ки в функции MillerRabinLow поставьте 10
- и в этом случае будут пробои в высших порядках;

ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 11:14     Эффективный алгоритм поиска простых чисел на С++ #48
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
я не хитрю
Проверяете число n порядка 1015 на простоту с помощью первых 100 чисел (хотя сами же выше пишете что надо искать делители среди первых sqrt( n ) чисел).
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
если бы кто-то в частности и вы ya_noob, разбирались в математике...
про sqrt( n ) я понимаю. как вы можете определить уровень моих познаний в математике, не спросив меня прямо об этом?
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
совершив 5-10 итерайций я уже найду составное число
Посмотрим:
Вот ваша программа из 29 поста (38 - то же самое, 40 - хитрость с "i <= 100"), немного измененная для считывания из входного потока и подсчета OPCount для каждого проверяемого числа
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
#include <cmath>
#include <iostream>
#include <cstdlib>
using namespace std;
 
bool isSimple(int num);
double OPCount = 0;
 
int main()
{
    int nCount  = 0;
    int x;
 
    while ( cin >> x ) 
    {
        isSimple( x );
        cout<<"Total count of operations : "<<OPCount<<endl;
        OPCount = 0;
    }
    system("pause");
    return 0;
}
 
bool isSimple(int num)
{
    int i;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= num / 10 && bSimple; i += 2)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}
Вот список простых чисел до миллиона (78489 штук):
primes.zip
только архивом. там лежит список из простых чисел в txt формате

Прогон программы по всем этим числам дает результат, который опровергает вашу оценку 5-10 итераций в 90 % случаев ПОДЧИСТУЮ. что вы на это скажете?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 11:35     Эффективный алгоритм поиска простых чисел на С++ #49
да тут я тут, просто отвлекся немного

Добавлено через 14 минут
Цитата Сообщение от ya_noob Посмотреть сообщение
Прогон программы по всем этим числам дает результат, который опровергает вашу оценку 5-10 итераций в 90 % случаев ПОДЧИСТУЮ
Чтобы не быть голословным и не утруждать вас я прогнал программу для тех чисел и получил 1,8 миллиардов итераций.
Прикинем, что получается: пусть все составные числа проверяются за 1 итерацию, тогда на проверку миллиона чисел приходится ~1,8 миллиардов итераций с хвостиком. следовательно в среднем 1.8 * 109 / 106 = ~1800 итераций на проверку одного числа. 5-10 итераций тут и рядом не стояли

Добавлено через 4 минуты
ох, маленько неточно выразился.
может быть и верно, что в 90 % случаев 5-10 итераций, но в оставшихся 10% случаях 22000 итераций на проверку. разительное отличие, которое игнорировать нельзя
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 11:47     Эффективный алгоритм поиска простых чисел на С++ #50
Цитата Сообщение от ya_noob Посмотреть сообщение
(хотя сами же выше пишете что надо искать делители среди первых sqrt( n ) чисел).
- я сказал это
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
При этом надо ещё посмотреть а не лежат ли все элементарные делителе скажем в пределах 2^8.
Цитата Сообщение от ya_noob Посмотреть сообщение
ох, маленько неточно выразился.
может быть и верно, что в 90 % случаев 5-10 итераций, но в оставшихся 10% случаях 22000 итераций на проверку. разительное отличие, которое игнорировать нельзя
- я проверю,

Цитата Сообщение от ya_noob Посмотреть сообщение
i <= num / 10
- у меня стоит в последней версии 100 я сейчас поставлю 256

Цитата Сообщение от ya_noob Посмотреть сообщение
while ( cin >> x )
* * {
* * * * isSimple( x );
* * * * cout<<"Total count of operations : "<<OPCount<<endl;
* * * * OPCount = 0;
* * }
Цитата Сообщение от ya_noob Посмотреть сообщение
я прогнал программу для тех чисел и получил 1,8 миллиардов итераций.
- ты ввёл
Цитата Сообщение от ya_noob Посмотреть сообщение
78489 штук
?
По поводу простых чисел из архива - я недоверяю непроверенным данным. Если и возьму в работу тот архив то только зная код который его создал либо источник.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 12:10     Эффективный алгоритм поиска простых чисел на С++ #51
по поводу ввода кучи чисел: в винде в cmd можно переправлять ввод вывод с помощью угловых скобок. в линухе скорее всего тоже что-то есть

по поводу непроверенных чисел из архива: по сути нет же разницы простые они или нет, просто для этого набора чисел количество итераций больше миллиарда. а то, что они меньше миллиона можно проверить "на глаз".
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 12:12     Эффективный алгоритм поиска простых чисел на С++ #52
Чтож теперь разберём по косточкам, как я уже отметил предел пробора 2^k зависит от порядка рассматриваемых чисел, для чисел из файла (а именно с максимумом) 999983 нам достаточно прогонки до 128 для адекватной проверки Есть смысл поработать над адаптивным выбором предела для нижней и верхней границей (для этого нужны исследования процессорная мощность и главное деньги). Я согласен провести исследования за пару К зелёных, найдёшь?
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
#include <cmath>
#include <fstream>
#include <iostream>
using namespace std;
 
bool isSimple(long num);
double OPCount = 0;
 
int main()
{
    long num     = 0;
    ofstream ofs("check.txt");
    ifstream ifs("primes.txt");
    if(!ifs.is_open())
        cout<<"ERROR OPEN primes.txt"<<endl;
    else
    while(!ifs.eof())
    {
        if(ifs>>num)
        if(isSimple(num))
        {
            cout<<"\r"<<num<<" SIMPLE ";
            ofs<<num<<" SIMPLE "<<endl;
        }
        else
        {
            cout<<"\r"<<num<<" NOT SIMPLE ";
            ofs<<num<<" NOT SIMPLE "<<endl;
            system("pause");
        }
        cout<<"Total count of operations : "<<OPCount;
    //    else
      //      continue;
        //if( nCount && nCount % 80 == 0 )
          //  system("pause");
    }
    ifs.close();
    ofs.close();
    cout<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long num)
{
    long i  = 0;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= 32 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        if(!bSimple)
            cout<<"DIVIDER : "<<i<<endl;
        OPCount += 1;
    } 
    return bSimple;
}
Чтобы ты тоже не утруждался у меня вышло 5 млн итераций ( с небольшим), т.е 5E6 / 78489 ~ 63 итераций на число
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 12:18     Эффективный алгоритм поиска простых чисел на С++ #53
ya_noob, вот результат работы кода который подан не как "Мартышкин труд", вот незадача
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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
 
// big numbers
 
double OPCount = 0;
long mulmod(long a, long b, long MOD){
    if (b == 0) return 0;
    long res = mulmod(a, b >> 1, MOD);//+1
    res += res;//+2
    res %= MOD;//+3
    OPCount += 4;
    return (b & 1)? (a + res) % MOD : res;//+4
}
 
bool witness(long a, long n) {
    long d = 1;
    long b = n - 1;
    for(int i = 63; i >= 0; i--)
    {
        if(b < pow(2.0, i)) continue;
        OPCount += 1;
        long x = d;//+1
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1){ return true; OPCount += 1;}//+1
        if ((b >> i) & 1) {d = mulmod(d, a, n);OPCount += 1;}
    }
    return (d != 1);
}
 
bool MillerRabin(long n, long tries) {
    for(int it = 0; it < tries; it++) 
    {
        OPCount += 2;//rand && %
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
// low numbers
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
bool witnessLow(int a, int n) {
    int d = 1;
    int b = n - 1;
    for(int i = 31; i >= 0; i--)
    {
        OPCount += 1;
        if(b < (1 << i)) continue;
        int x = d;
        OPCount += 1;
        d = (long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) {return true; OPCount += 1;}
        if((b >> i) & 1){ d = (long(d) * a) % n; OPCount += 1;}
    }
    OPCount += 1;
    return (d != 1);
}
 
bool MillerRabinLow(int n) 
{
    OPCount += 1;
      if(n == 2) return true;
    if(witnessLow(2, n)) return false;
    return true;
}
 
bool test(long c)
{
    OPCount += 1;
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
/*  ofstream ofs("out.txt");
    int nCount  = 0;
    for(int num = 2; num <= 3571; num++)
    {
        if(test(num))
        {
            cout<<(nCount++)<<" - "<<num<<endl;
            ofs<<num<<endl;
        }
      //  else
      //      continue;
      //  if( nCount && nCount % 80 == 0 )
      //      system("pause");
    }
    ofs.close();*/
    /*
        int arr[] = {2047, 3277};
    for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
    {
        cout<<arr[i]<<" - ";
        if(test(arr[i]))
            cout<<"SIMPLE"<<endl;
        else
            cout<<"NOT SIMPLE"<<endl;
    }
    */
    long num     = 0;
    ofstream ofs("check.txt");
    ifstream ifs("primes.txt");
    if(!ifs.is_open())
        cout<<"ERROR OPEN primes.txt"<<endl;
    else
    while(!ifs.eof())
    {
        if(ifs>>num)
        if(test(num))
        {
            cout<<"\r"<<num<<" SIMPLE ";
            ofs<<num<<" SIMPLE "<<endl;
        }
        else
        {
            cout<<"\r"<<num<<" NOT SIMPLE ";
            ofs<<num<<" NOT SIMPLE "<<endl;
            system("pause");
        }
        cout<<"Total count of operations : "<<OPCount;
    //    else
      //      continue;
        //if( nCount && nCount % 80 == 0 )
          //  system("pause");
    }
    ifs.close();
    ofs.close();
    cout<<endl;
    system("pause");
    return 0;
    return 0; 
}
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 12:20     Эффективный алгоритм поиска простых чисел на С++ #54
Потом я решил как сказал господин Ternsip, увеличить точность и поставить 10-ку куда он просил
bool MillerRabinLow(int n)
{
OPCount += 1;
if(n == 2) return true;
if(witnessLow(10, n)) return false;
return true;
}
Вот блин
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 12:22     Эффективный алгоритм поиска простых чисел на С++ #55
Потом я всё таки решил поглядеть сколько же итераций займёт код господина Ternsip, и вот чёрт опять что то не то, подскажи м.б я что то не так делал?
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
03.05.2013, 12:23
  #56

Не по теме:

Я бы на чьём-то месте просто закрыл рот и пошёл занялся делом...

Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 12:33     Эффективный алгоритм поиска простых чисел на С++ #57
-=ЮрА=-, ваша программа всё ещё не работает 12312449 число не простое делитель 47

Добавлено через 2 минуты
-=ЮрА=-, Вот последняя версия, чтобы вопросов не возникало на счёт правильности
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
 
using namespace std;
 
// big numbers
 
long long mulmod(long long a, long long b, long long MOD){
    if (b == 0) return 0;
    long long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long long a, long long n) {
    long long d = 1;
    long long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < pow(2.0, i)) continue;
        long long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries) {
    for(int it = 0; it < tries; it++) {
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
int main(){
    long long n = 5;
    cout << MillerRabin(n, 19);
    return 0; 
}


Добавлено через 1 минуту
-=ЮрА=-, тест Миллера Рабина работает за O (log3(N))
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 12:47     Эффективный алгоритм поиска простых чисел на С++ #58
Цитата Сообщение от Ternsip Посмотреть сообщение
ваша программа всё ещё не работает 12312449
- я сделал тест для
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
999983
где достаточно
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
прогонки до 128 для адекватной проверки
. Повторюсь
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Есть смысл поработать над адаптивным выбором предела для нижней и верхней границей (для этого нужны исследования процессорная мощность и главное деньги). Я согласен провести исследования за пару К зелёных, найдёшь?
Добавлено через 15 секунд
Цитата Сообщение от Ternsip Посмотреть сообщение
=ЮрА=-, Вот последняя версия, чтобы вопросов не возникало на счёт правильности
- окей момент
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 12:58     Эффективный алгоритм поиска простых чисел на С++ #59
Ternsip, ну слава богу ты поставил 19, а то 10-кой на интервале 1-999983 было 70 тыс ошибок. А теперь сравни отработку для моего и твоего алгоритмов для чисел из primes (я остановил на миллиарде операций, сил не стало ждать + это я ещё считаю pow(x, n) как 1 операцию а ведь это n операций)
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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
 
// big numbers
 
double OPCount = 0;
long mulmod(long a, long b, long MOD)
{
    if (b == 0) return 0;
    long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    OPCount += 4;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long a, long n) {
    long d = 1;
    long b = n - 1;
    for(int i = 63; i >= 0; i--)
    {
        if(b < pow(2.0, i)) continue;
        OPCount += 1;//õîòÿ ñëîæГ*îñòü pow(x, n) ГЅГІГ® n
        long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1){ return true; OPCount += 1;}//+1
        if ((b >> i) & 1){d = mulmod(d, a, n);OPCount += 1;}
    }
    return (d != 1);
}
 
bool MillerRabin(long n, long tries) 
{
    for(int it = 0; it < tries; it++) 
    {
        OPCount += 1;
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
int main()
{
    long nCount  = 0;
    long num     = 0;
    ofstream ofs("check.txt");
    ifstream ifs("primes.txt");
    if(!ifs.is_open())
        cout<<"ERROR OPEN primes.txt"<<endl;
    else
    while(!ifs.eof())
    {
        if(ifs>>num)
        if(MillerRabin(num, 19))
        {
            cout<<"\r"<<num<<" SIMPLE ";
            ofs<<num<<" SIMPLE "<<endl;
        }
        else
        {
            cout<<"\r"<<num<<" NOT SIMPLE ";
            ofs<<num<<" NOT SIMPLE "<<endl;
            //system("pause");
            nCount++;
        }
        cout<<"Total count of operations : "<<OPCount<<" Nerror : "<<nCount;
    //    else
      //      continue;
        //if( nCount && nCount % 80 == 0 )
          //  system("pause");
    }
    ifs.close();
    ofs.close();
    cout<<endl;
    system("pause");
    return 0;
}
Твой код провалится на очень больших числах, за несколько штук зелёных могу показать каких.
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 13:01     Эффективный алгоритм поиска простых чисел на С++
Еще ссылки по теме:

C++ функция поиска простых чисел
Алгоритм нахождения простых чисел C++
Алгоритм нахождения простых чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
03.05.2013, 13:01     Эффективный алгоритм поиска простых чисел на С++
  #60

Не по теме:

ЗЫ

Цитата Сообщение от Ternsip Посмотреть сообщение
тест Миллера Рабина работает за O (log3(N))
- у тебя код на половине чисел дал 1 млрд операций если ещё возведение в степень считать как 1 операцию.

Yandex
Объявления
03.05.2013, 13:01     Эффективный алгоритм поиска простых чисел на С++
Ответ Создать тему
Опции темы

Текущее время: 06:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru