Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.63/51: Рейтинг темы: голосов - 51, средняя оценка - 4.63
2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
1

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

02.05.2013, 11:41. Просмотров 10447. Ответов 94
Метки нет (Все метки)

Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.05.2013, 11:41
Ответы с готовыми решениями:

Алгоритм поиска простых чисел
Доброго времени суток. Помогите пожалуйста с алгоритмом поиска простых чисел в массиве. Искал...

Алгоритм поиска n простых чисел
Помогите, пожалуйста, составить батник, находящий простые числа в заданном интервале.

Алгоритм поиска простых чисел.
Нашел пример алгоритма, используемого для получения всех простых чисел от 2 до заданного путем...

Реализовать алгоритм поиска простых чисел
Реализовать алгоритм поиска простых чисел (&quot;Решето Эратосфена&quot;) до 200. Подскажите как плиз

94
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 23:06 41
-=ЮрА=-,Ваша последняя программа по-прежнему не работает, число 1244042141 не простое, а она говорит, что простое. 1244042141 делится на 181
0
Заблокирован
Автор FAQ
03.05.2013, 06:46 42
Мой алгоритм работает,до ИНТ_МАХ. Хорошо через пару часов еще немного доработав получу универсальный код,ты лучше свой код доработай по тем замечаниям которые даны выше.Поверь я доведу до момента когда ответишь за свои слова, держись малыш)))
0
_
317 / 151 / 27
Регистрация: 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: -=ЮрА=-, зря вы так про справочники говорите, они помогают сократить время на написание программ, избегать глупых ошибок, неверных и неэффективных (в вашем случае) алгоритмов.
на основе вашей неприязни к справочникам могу предположить, что и библиотеками готовых алгоритмов вы не пользуетесь, и каждый раз всё пишете сначала. Мартышкин труд.
0
Заблокирован
Автор 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 Посмотреть сообщение
Позволю себе поучаствовать в этом безобразии, т.к. делать нечего.
- лучше займись своими делами

0
Заблокирован
Автор 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-ти сотнях...
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 10:50 46
-=ЮрА=-, повысьте точность if(witnessLow(2, n)) return false; вместо 2-ки в функции MillerRabinLow поставьте 10
0
Заблокирован
Автор FAQ
03.05.2013, 11:05 47
Ternsip, я не хочу ничего повышать, я также мог сказать повысь точность пробора написав вместо 100 256, твой код уже лажает в первых 500 числах, если я повышу точность в твоём коде то в столько же раз упадёт его производительность. Разговор шёл о том что я якобы толкаю туфту юзерам, так вот туфту впарил ты бедолаге ТС.

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

Не по теме:

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

0
_
317 / 151 / 27
Регистрация: 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 % случаев ПОДЧИСТУЮ. что вы на это скажете?
0
_
317 / 151 / 27
Регистрация: 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 итераций на проверку. разительное отличие, которое игнорировать нельзя
0
Заблокирован
Автор 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 штук
?
По поводу простых чисел из архива - я недоверяю непроверенным данным. Если и возьму в работу тот архив то только зная код который его создал либо источник.
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 12:10 51
по поводу ввода кучи чисел: в винде в cmd можно переправлять ввод вывод с помощью угловых скобок. в линухе скорее всего тоже что-то есть

по поводу непроверенных чисел из архива: по сути нет же разницы простые они или нет, просто для этого набора чисел количество итераций больше миллиарда. а то, что они меньше миллиона можно проверить "на глаз".
0
Заблокирован
Автор 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 итераций на число
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
Заблокирован
Автор 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; 
}
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;
}
Вот блин
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
Заблокирован
Автор FAQ
03.05.2013, 12:22 55
Потом я всё таки решил поглядеть сколько же итераций займёт код господина Ternsip, и вот чёрт опять что то не то, подскажи м.б я что то не так делал?
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
03.05.2013, 12:23
  #56

Не по теме:

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

0
667 / 195 / 29
Регистрация: 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))
0
Заблокирован
Автор FAQ
03.05.2013, 12:47 58
Цитата Сообщение от Ternsip Посмотреть сообщение
ваша программа всё ещё не работает 12312449
- я сделал тест для
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
999983
где достаточно
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
прогонки до 128 для адекватной проверки
. Повторюсь
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Есть смысл поработать над адаптивным выбором предела для нижней и верхней границей (для этого нужны исследования процессорная мощность и главное деньги). Я согласен провести исследования за пару К зелёных, найдёшь?
Добавлено через 15 секунд
Цитата Сообщение от Ternsip Посмотреть сообщение
=ЮрА=-, Вот последняя версия, чтобы вопросов не возникало на счёт правильности
- окей момент
0
Заблокирован
Автор 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;
}
Твой код провалится на очень больших числах, за несколько штук зелёных могу показать каких.
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
03.05.2013, 13:01     Эффективный алгоритм поиска простых чисел на С++
  #60

Не по теме:

ЗЫ

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

0
03.05.2013, 13:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 13:01
Привет! Вот еще темы с ответами:

Cоставить алгоритм поиска N простых чисел
составить алгоритм поиска N простых чисел

Алгоритм поиска целых простых чисел
Предлагаю простой алгоритм проверки и поиска простых чисел, приглашаю к сотрудничеству в написании...

Линейный алгоритм поиска простых чисел
Здравствуйте, помогите пожалуйста написать линейный алгоритм на языке си, желательно с...

Алгоритм поиска количества простых чисел в заданном массиве
алгоритм поиск количества простых чисел в заданном целочисленном массиве из 50 элементов. Помогите...


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.