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

@NaikoN · Регистрация: 01.05.2013

Студворк — интернет-сервис помощи студентам

Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 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 · 03.05.2013, 18:25

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

@abit · 03.05.2013, 18:28

кстати отличная инфа по этой теме - http://e-maxx.ru/algo/bpsw
там отметьте кроме теста Миллера-Рабина ещё вводится Сильный тест Лукаса-Селфриджа
не спроста это, одного теста там не достаточно, как у вас

Ternsip · 03.05.2013, 18:30

abit, этот сайт делал наш студент Иванов Максим, я прекрасно ознакомлен со всеми статьями на этом портале.

@abit · 03.05.2013, 18:46

Ternsip,
тогда ещё лучше, при всём уважении цитирую с сайта

(факт) тест Миллера-Рабина и тест Лукаса-Селфриджа если и ошибаются, то только в одну сторону: некоторые составные числа этими алгоритмами опознаются как простые

это факт у вас написано, значит отельный тест точно ошибается, а мой гарантирует 100%, далее - вы так же пишите что до 10^15 ошибок одновременно обоих нет - ок, я верю и правда раз у вас оптимизация аж до log^3(N) непонятно на каком хламе вы три года это проверяли... хотя я плохо прикинул сумму сложностей для этого теста и для обычного теста на всех числах от 1 до 10^15, но почему-то в 3 года непрерывной работы кучи нормальных компьютеров на выполнение обоих тестов мне не верится

а так - со статьёй согласен, вопросов не имею, если вы опираетесь на это, не доказано на больших числах - ну и ладно, математики всегда хромают - за 500 лет не могут задачу о трёх телах решить, за 100 лет от них даже не решение уравнения Навье - Стокса хотят, а только просят доказать, что оно вообще существуют и миллион долларов дают, а те не могут

@-=ЮрА=- · 03.05.2013, 20:27

Сообщение от Ternsip

-=ЮрА=-, напишите код, я его проверю на контесторе, я сомневаюсь в справедливости сказанного. В вашем рассуждении вы делаете ужасную ошибку, вы думаете, что через разряды, не зависимо от числа, можно проверять его на делимость....

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix} a & b \\ k & 1EN \\ 10*k & 1EN /(10*k) = 1EN - 1\\ 100*k & 1EN /(100*k) = 1EN - 2 \\ .... & \\ k*E(N/2) & 1EN /[k*E(N/2)] = 1E(N/2) \end{matrix}$
Я уже приводил выкладки, проверить все делители можно до SQRT(N) - прошу не надо спорить там где это очевидно.
(Ещё раз если a*b = c и a < SQRT(c) то b > SQRT(c) а стало быть баланс а и b существует только у корня из числа, далее идёт повторение делителей).На счёт кода - вот пока неоптимизированный вариант (в данный момент усиленно думаю над нижней границей проверки, верней как сделать начало не с 11 а поднимать степень и у начала)

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 <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    long long nCount  = 0;
    long long num     = 0;
    for(num = 2; num < 999984; num++)
    {
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    cout<<"\nOTHER TESTS : "<<endl;
    if(isSimple(9999999900000001))
        cout<<"IS SIMPLE"<<endl;
    if(isSimple(2147483647))
        cout<<"IS SIMPLE"<<endl;
    if(isSimple(1244042141))
        cout<<"IS SIMPLE"<<endl;
    else
        cout<<"NOT SIMPLE"<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long long i     = 0;
    long long limit = 10;
    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;
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
          OPCount += 1;
    }
    //3.2 чтобы перкрыть корень sqrt 10 максимум что можем получить
    limit = 32*limit;
    limit = limit / 10;
    OPCount += 2;
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}

Без сомнения на 1Е6 чисел даже в утяжелённом (100% надёжном варианте), алгоритм лучше вашего Ternsip, зачем упорствовать?Надо думать как ускорить и уменьшить число операций, а не освистывать

Давайте ещё раз по полочкам

Сообщение от Ternsip

ля абсолютного теста я возьму несколько больших чисел (около 10 шт) и просумирую время выполнения вашего и моего алгоритма на них, в случае, если вы сможете написать код, который работает правильно

- я пока могу гаранитровать эффективность на числах думаю 10E7-8 (ну так и думаю я всего 2-й день). Также для адекватной оценки прошу в вашем коде в строчке pow проставить не +1 а плюс i в зависимости от показателя степени (я занижаю число операций в вашем алгоритме чуть ли не в 100 раз)...

@-=ЮрА=- · 03.05.2013, 20:32

Не по теме:

Я вышел, возможно до завтра и так тема отняла кучу времени, у меня хватает ещё дел...

Ternsip · 03.05.2013, 20:53

-=ЮрА=-, а вот теперь запустите эту программу, не меняя её на тесте 9999999900000001, работает 3 секунды на http://codeforces.com/, когда Рабин пашет за 0 ms

Добавлено через 1 минуту
-=ЮрА=-, а вот на этом тесте 909090909090909091 рабин пашет 15 ms

Добавлено через 1 минуту
-=ЮрА=-, вот ещё тест 0 ms работает 1111111111111111111
на всех этих тестах у вас > 3 секунд

Добавлено через 1 минуту
-=ЮрА=-, на 1111111111111111111 у вас ваще за 10 секунд перехлестнуло

@abit · 03.05.2013, 21:37

salam,
да бросьте вы, чистый Миллер-Рабин доказано не работает верно и вроде Ternsip с этим не спорит, а вот совместно с Лукаса-Селфриджа - я допустил что это работает, но это тоже не доказано точно
и я даже привёл контр-пример - вполне реально замутить нечёткую нейронную сеть (но это дело отдельных исследований, а они судя по статье занимались этим 3 года минимум), которая действительно в независимости от числа N определит простоту числа с некоторой вероятностью, может быть меньше будет вероятность, а может быть больше, всё зависит от реализации, но отдельно одного теста Миллера-Рабина можно потягаться, по быстродействию все шансы выиграть, потому что вряд ли O(log^3(N)) будет быстрее O(1)... относительно обоих тестов - не знаю, надо вникать в проблему

@BumerangSP · 03.05.2013, 22:29

Комментарий модератора

Товарищи. Если вы и дальше будете переходить на личности, выяснять отношения и оффтопить - тему придется закрыть, а нарушителей - наказать.

@-=ЮрА=- · 03.05.2013, 23:19

Внизу коды и сравнительная отработка, для значений до 1Е6 и до 1Е7 включительно
(больший объём проверять для меня с моим 1ядерным ПК 2,7 ГГц слишком долго),
буду благодарен за сравнительные тесты на больших порядках скажем до 1Е8-10. В своём коде изъял домножение на 3.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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    time_t beg;
    time_t end;
    time(&beg);
    long long nCount  = 0;
    for(long long num = 2; num < 1E7; num++)
    {
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    time(&end);
    system("cls");
    cout<<"\rITERS : "<<OPCount
        <<" COUNT : "<<nCount;
    cout<<"\n\tSTATISTIC:"<<endl;
    cout<<"program started : "<<asctime(localtime(&beg));
    cout<<"program stopped : "<<asctime(localtime(&end));
    cout<<"work time : "<<difftime(end, beg)<<endl;
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long long i     = 0;
    long long limit = 10;
    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;
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
          OPCount += 1;
    }
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}

Код Ternsip

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

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 <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
 
// big numbers
 
double OPCount = 0;
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);//+1
    res += res;//+2
    res %= MOD;//+3
    OPCount += 4;
    return (b & 1)? (a + res) % MOD : res;//+4
}
 
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;
        OPCount += i;//как того требует pow(i)
        long 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 long n, long 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 long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) {return true; OPCount += 1;}
        if((b >> i) & 1){ d = (long long(d) * a) % n; OPCount += 1;}
    }
    OPCount += 1;
    return (d != 1);
}
 
bool MillerRabinLow(int n) 
{
    OPCount += 1;
      if(n == 2) return true;
    if(witnessLow(19, n)) return false;
    return true;
}
 
bool test(long long c)
{
    OPCount += 1;
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
    time_t beg;
    time_t end;
    time(&beg);
    long long nCount  = 0;
    for(long long num = 2; num < 1E7; num++)
    {
        if(test(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    time(&end);
    cout<<"\n\tSTATISTIC:"<<endl;
    cout<<"program started : "<<asctime(localtime(&beg));
    cout<<"program stopped : "<<asctime(localtime(&end));
    cout<<"work time : "<<difftime(end, beg)<<endl;
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}

В заключение ещё раз прошу либо писать по сути, либо не писать вообще, ваши предположения подкрепляйте тестами кодами, скриншотами. Остаётся добавить что судя из отработки на порядке 1Е7 мой код выдал 664579 против 664780 простых чисел у Ternsip (что может косвенно говорить о новых брежах алгоритма по типу отмеченных в посте 53. Хотелось бы узнать точное число простых чисел на промежутке 1 - 1Е7

@-=ЮрА=- · 04.05.2013, 00:29

ЗЫ: Хотя решил для себя проверить код Ternsip, для этого соорудил сэйв результатов от 1Е6 до 1Е7 и разобрал моим алгоритмом (скрин и алгоритмы прилагаю)
Генератор чисел на базе кода Ternsip,

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

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
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
using namespace std;
 
// big numbers
 
double OPCount = 0;
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);//+1
    res += res;//+2
    res %= MOD;//+3
    OPCount += 4;
    return (b & 1)? (a + res) % MOD : res;//+4
}
 
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;
        OPCount += i;//как того требует pow(i)
        long 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 long n, long 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 long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) {return true; OPCount += 1;}
        if((b >> i) & 1){ d = (long long(d) * a) % n; OPCount += 1;}
    }
    OPCount += 1;
    return (d != 1);
}
 
bool MillerRabinLow(int n) 
{
    OPCount += 1;
      if(n == 2) return true;
    if(witnessLow(19, n)) return false;
    return true;
}
 
bool test(long long c)
{
    OPCount += 1;
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
    time_t beg;
    time_t end;
    time(&beg);
    ofstream ofs("1E61E7.txt");
    long long nCount  = 0;
    for(long long num = 1E6; num < 1E7; num++)
    {
        if(test(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
            if( ofs.is_open() )
                ofs<<num<<endl;
        }
    }
    time(&end);
    ofs.close();
    cout<<"\n\tSTATISTIC:"<<endl;
    cout<<"program started : "<<asctime(localtime(&beg));
    cout<<"program stopped : "<<asctime(localtime(&end));
    cout<<"work time : "<<difftime(end, beg)<<endl;
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}

Код проверки значений

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

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
#include <cmath>
#include <fstream>
#include <iostream>
using namespace std;
 
bool isSimple(long num);
 
int main()
{
    long num;
    long nCount  = 0;
    ifstream ifs("1E61E7.txt");
    if(!ifs.is_open())
        cout<<"ERROR OPEN 1E61E7.txt"<<endl;
    else
    while(!ifs.eof())
    {
        if(ifs>>num)
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM : "<<num<<" IS SIMPLE ";
        }
        else
            cout<<"\rNUM : "<<num<<" NOT SIMPLE "<<endl;
    }
    system("pause");
    return 0;
}
 
bool isSimple(long num)
{
    long i     = 0;
    long limit = 10;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        if( i != num )
            bSimple = num % i != 0;
        if(!bSimple)
            cout<<"\t\t\tDIVISOR : "<<i;
        
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
    }
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        if(!bSimple)
            cout<<"\t\tDIVISOR : "<<i;
    } 
    return bSimple;
}

Как видим даже с увеличенной точностью

Сообщение от Ternsip

-=ЮрА=-, Вот последняя версия, чтобы вопросов не возникало на счёт правильности

вопросы всё же возникают, около 68 штук
Список вопросов

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

NUM : 1010651 NOT SIMPLE DIVISOR : 821
NUM : 1032533 NOT SIMPLE DIVISOR : 587
NUM : 1056331 NOT SIMPLE DIVISOR : 727
NUM : 1090987 NOT SIMPLE DIVISOR : 853
NUM : 1122337 NOT SIMPLE DIVISOR : 241
NUM : 1314631 NOT SIMPLE DIVISOR : 811
NUM : 1314721 NOT SIMPLE DIVISOR : 37
NUM : 1333603 NOT SIMPLE DIVISOR : 1033
NUM : 1373653 NOT SIMPLE DIVISOR : 829
NUM : 1440217 NOT SIMPLE DIVISOR : 73
NUM : 1491511 NOT SIMPLE DIVISOR : 7
NUM : 1493857 NOT SIMPLE DIVISOR : 547
NUM : 1537381 NOT SIMPLE DIVISOR : 877
NUM : 1539287 NOT SIMPLE DIVISOR : 227
NUM : 1566589 NOT SIMPLE DIVISOR : 229
NUM : 1638501 NOT SIMPLE DIVISOR : 3
NUM : 1645393 NOT SIMPLE DIVISOR : 113
NUM : 1746553 NOT SIMPLE DIVISOR : 367
NUM : 1748921 NOT SIMPLE DIVISOR : 691
NUM : 1803601 NOT SIMPLE DIVISOR : 601
NUM : 1805131 NOT SIMPLE DIVISOR : 271
NUM : 1809457 NOT SIMPLE DIVISOR : 13
NUM : 1815049 NOT SIMPLE DIVISOR : 487
NUM : 1880082 NOT SIMPLE DIVISOR : 2
NUM : 1904033 NOT SIMPLE DIVISOR : 797
NUM : 1968557 NOT SIMPLE DIVISOR : 1087
NUM : 1975231 NOT SIMPLE DIVISOR : 103
NUM : 2030341 NOT SIMPLE DIVISOR : 823
NUM : 2255843 NOT SIMPLE DIVISOR : 823
NUM : 2281049 NOT SIMPLE DIVISOR : 617
NUM : 2310829 NOT SIMPLE DIVISOR : 79
NUM : 2337301 NOT SIMPLE DIVISOR : 883
NUM : 2593909 NOT SIMPLE DIVISOR : 73
NUM : 2604331 NOT SIMPLE DIVISOR : 571
NUM : 2671601 NOT SIMPLE DIVISOR : 17
NUM : 2687089 NOT SIMPLE DIVISOR : 577
NUM : 2913181 NOT SIMPLE DIVISOR : 1151
NUM : 2926381 NOT SIMPLE DIVISOR : 647
NUM : 2955451 NOT SIMPLE DIVISOR : 367
NUM : 2995147 NOT SIMPLE DIVISOR : 463
NUM : 3052063 NOT SIMPLE DIVISOR : 7
NUM : 3125281 NOT SIMPLE DIVISOR : 1021
NUM : 3139319 NOT SIMPLE DIVISOR : 283
NUM : 3231229 NOT SIMPLE DIVISOR : 617
NUM : 3342827 NOT SIMPLE DIVISOR : 1493
NUM : 3366631 NOT SIMPLE DIVISOR : 31
NUM : 3488347 NOT SIMPLE DIVISOR : 733
NUM : 3523801 NOT SIMPLE DIVISOR : 31
NUM : 3597889 NOT SIMPLE DIVISOR : 241
NUM : 3604201 NOT SIMPLE DIVISOR : 1201
NUM : 3632593 NOT SIMPLE DIVISOR : 241
NUM : 3647621 NOT SIMPLE DIVISOR : 1103
NUM : 3736011 NOT SIMPLE DIVISOR : 3
NUM : 3808603 NOT SIMPLE DIVISOR : 127
NUM : 3815011 NOT SIMPLE DIVISOR : 691
NUM : 3873097 NOT SIMPLE DIVISOR : 109
NUM : 3913003 NOT SIMPLE DIVISOR : 1399
NUM : 3942271 NOT SIMPLE DIVISOR : 811
NUM : 3985921 NOT SIMPLE DIVISOR : 1153
NUM : 4095961 NOT SIMPLE DIVISOR : 929
NUM : 4150387 NOT SIMPLE DIVISOR : 1019
NUM : 4224533 NOT SIMPLE DIVISOR : 1187
NUM : 4384693 NOT SIMPLE DIVISOR : 1873
NUM : 4453721 NOT SIMPLE DIVISOR : 461
NUM : 4592407 NOT SIMPLE DIVISOR : 157
NUM : 4698913 NOT SIMPLE DIVISOR : 1009
NUM : 4797703 NOT SIMPLE DIVISOR : 59
NUM : 4808557 NOT SIMPLE DIVISOR : 13
NUM : 4931941 NOT SIMPLE DIVISOR : 7
NUM : 5029711 NOT SIMPLE DIVISOR : 71
NUM : 5262355 NOT SIMPLE DIVISOR : 5
NUM : 5292631 NOT SIMPLE DIVISOR : 1627
NUM : 5481451 NOT SIMPLE DIVISOR : 31
NUM : 5575501 NOT SIMPLE DIVISOR : 1181
NUM : 5646989 NOT SIMPLE DIVISOR : 293
NUM : 5902849 NOT SIMPLE DIVISOR : 733
NUM : 5903497 NOT SIMPLE DIVISOR : 1087
NUM : 5979247 NOT SIMPLE DIVISOR : 1223
NUM : 5982949 NOT SIMPLE DIVISOR : 7
NUM : 6431473 NOT SIMPLE DIVISOR : 181
NUM : 6542761 NOT SIMPLE DIVISOR : 421
NUM : 6577121 NOT SIMPLE DIVISOR : 1481
NUM : 6594901 NOT SIMPLE DIVISOR : 1483
NUM : 6637546 NOT SIMPLE DIVISOR : 2
NUM : 6746749 NOT SIMPLE DIVISOR : 467
NUM : 6765826 NOT SIMPLE DIVISOR : 2
NUM : 6986827 NOT SIMPLE DIVISOR : 67
NUM : 7120513 NOT SIMPLE DIVISOR : 1009
NUM : 7126129 NOT SIMPLE DIVISOR : 241
NUM : 7344947 NOT SIMPLE DIVISOR : 2213
NUM : 7455709 NOT SIMPLE DIVISOR : 73
NUM : 7480549 NOT SIMPLE DIVISOR : 37
NUM : 7526513 NOT SIMPLE DIVISOR : 1181
NUM : 7648033 NOT SIMPLE DIVISOR : 1597
NUM : 7686647 NOT SIMPLE DIVISOR : 2531
NUM : 7788943 NOT SIMPLE DIVISOR : 883
NUM : 7828201 NOT SIMPLE DIVISOR : 37
NUM : 7859707 NOT SIMPLE DIVISOR : 887
NUM : 7879681 NOT SIMPLE DIVISOR : 1621
NUM : 7971451 NOT SIMPLE DIVISOR : 457
NUM : 8428645 NOT SIMPLE DIVISOR : 5
NUM : 8614033 NOT SIMPLE DIVISOR : 577
NUM : 8697121 NOT SIMPLE DIVISOR : 577
NUM : 8899661 NOT SIMPLE DIVISOR : 2311
NUM : 8936722 NOT SIMPLE DIVISOR : 2
NUM : 9080191 NOT SIMPLE DIVISOR : 2131
NUM : 9206623 NOT SIMPLE DIVISOR : 307
NUM : 9345541 NOT SIMPLE DIVISOR : 59
NUM : 9439201 NOT SIMPLE DIVISOR : 61
NUM : 9483706 NOT SIMPLE DIVISOR : 2
NUM : 9487153 NOT SIMPLE DIVISOR : 13
NUM : 9493903 NOT SIMPLE DIVISOR : 2179
NUM : 9504191 NOT SIMPLE DIVISOR : 1259
NUM : 9591661 NOT SIMPLE DIVISOR : 1171
NUM : 9707377 NOT SIMPLE DIVISOR : 1039
NUM : 9745291 NOT SIMPLE DIVISOR : 1669
NUM : 9964753 NOT SIMPLE DIVISOR : 337
NUM : 9999991 IS SIMPLE Для продолжения нажмите любую клавишу . . .

@abit · 04.05.2013, 01:18

BumerangSP,

Ты, Зин, на грубость нарываешься!

(c) Высоцкий

а вот никого я не оскоблял! я вступился за
-=ЮрА=-,
и скажу почему... вы скомпильте и запустите код, что нам дал
Ternsip, вот тут - Эффективный алгоритм поиска простых чисел на С++

я не знаю как у вас, у меня под виртуалкой Win XP SP3 комп с сего кода перегружается, а в Linux сия программа виснет, да выдавая ответ 1 на 5, согласен простое число, 0 на 6 - да не простое, и на 121 - выдаёт 0, но извините сия программа вызывает перегруз виртуалки Win Xp3, я молчу что она намертво виснет под линуксом и приходится её убивать... и что вообще значит этот 0?

@isaak · 06.05.2013, 11:31

Сообщение от -=ЮрА=-

Внизу коды и сравнительная отработка, для значений до 1Е6 и до 1Е7 включительно
(больший объём проверять для меня с моим 1ядерным ПК 2,7 ГГц слишком долго),
буду благодарен за сравнительные тесты на больших порядках скажем до 1Е8-10. В своём коде изъял домножение на 3.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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    time_t beg;
    time_t end;
    time(&beg);
    long long nCount  = 0;
    for(long long num = 2; num < 1E7; num++)
    {
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    time(&end);
    system("cls");
    cout<<"\rITERS : "<<OPCount
        <<" COUNT : "<<nCount;
    cout<<"\n\tSTATISTIC:"<<endl;
    cout<<"program started : "<<asctime(localtime(&beg));
    cout<<"program stopped : "<<asctime(localtime(&end));
    cout<<"work time : "<<difftime(end, beg)<<endl;
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long long i     = 0;
    long long limit = 10;
    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;
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
          OPCount += 1;
    }
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}

-=ЮрА=- вот протестировал твой код при значении 1Е8-10.

@-=ЮрА=- · 06.05.2013, 12:57

Не по теме:

isaak, а можешь теперь протестировать код?

Сообщение от -=ЮрА=-

Генератор чисел на базе кода Ternsip,
Кликните здесь для просмотра всего текста

- я хочу увидеть сколько итераций сделает тот алгоритм

@isaak · 06.05.2013, 23:35

-=ЮрА=- если этот код, то вот результат

Новые блоги и статьи Все статьи Все блоги /
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	03.05.2013, 18:25
	abit, Эффективный алгоритм поиска простых чисел на С++ 0

@abit 870 / 529 / 149 Регистрация: 03.02.2013 Сообщений: 1,858
	03.05.2013, 18:28
	кстати отличная инфа по этой теме - http://e-maxx.ru/algo/bpsw там отметьте кроме теста Миллера-Рабина ещё вводится Сильный тест Лукаса-Селфриджа не спроста это, одного теста там не достаточно, как у вас 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	03.05.2013, 18:30
	abit, этот сайт делал наш студент Иванов Максим, я прекрасно ознакомлен со всеми статьями на этом портале. 0

@-=ЮрА=-
	03.05.2013, 20:32
	Не по теме: Я вышел, возможно до завтра и так тема отняла кучу времени, у меня хватает ещё дел... 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	03.05.2013, 20:53
	-=ЮрА=-, а вот теперь запустите эту программу, не меняя её на тесте 9999999900000001, работает 3 секунды на http://codeforces.com/, когда Рабин пашет за 0 ms Добавлено через 1 минуту -=ЮрА=-, а вот на этом тесте 909090909090909091 рабин пашет 15 ms Добавлено через 1 минуту -=ЮрА=-, вот ещё тест 0 ms работает 1111111111111111111 на всех этих тестах у вас > 3 секунд Добавлено через 1 минуту -=ЮрА=-, на 1111111111111111111 у вас ваще за 10 секунд перехлестнуло 0

@abit 870 / 529 / 149 Регистрация: 03.02.2013 Сообщений: 1,858
	03.05.2013, 21:37
	salam, да бросьте вы, чистый Миллер-Рабин доказано не работает верно и вроде Ternsip с этим не спорит, а вот совместно с Лукаса-Селфриджа - я допустил что это работает, но это тоже не доказано точно и я даже привёл контр-пример - вполне реально замутить нечёткую нейронную сеть (но это дело отдельных исследований, а они судя по статье занимались этим 3 года минимум), которая действительно в независимости от числа N определит простоту числа с некоторой вероятностью, может быть меньше будет вероятность, а может быть больше, всё зависит от реализации, но отдельно одного теста Миллера-Рабина можно потягаться, по быстродействию все шансы выиграть, потому что вряд ли O(log^3(N)) будет быстрее O(1)... относительно обоих тестов - не знаю, надо вникать в проблему 0

@isaak 90 / 125 / 28 Регистрация: 17.10.2010 Сообщений: 1,333
	06.05.2013, 23:35
	-=ЮрА=- если этот код, то вот результат Миниатюры 1