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

@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 · 02.05.2013, 17:25

-=ЮрА=-, теперь согласен.

хоть это и не самое оптимальное решение.

@-=ЮрА=- · 02.05.2013, 17:33

Это чтоб проскакивать нормально по 80 чисел, в спешке паузу не довёл

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
        else
            continue;
        if( nCount && nCount % 80 == 0 )
            system("pause");
    }
    return 0;
}

Добавлено через 3 минуты
NaikoN, надеюсь ты зайдёшь и посомтришь пост 19

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

-=ЮрА=-, теперь согласен. хоть это и не самое оптимальное решение.

- А мы сейчас проверим число операций в моем и твоём алгоритме

Добавлено через 1 минуту
Итак Ternsip, приступим , покажи мне пожалуйста свой завершённый код проверки простого сложного числа, жду

Ternsip · 02.05.2013, 17:35

-=ЮрА=-, оооо, спасибо)
тогда проверьте отдельно для числа 9999999900000001
на тесте Миллера Рабина, котый я в начале привёл

Добавлено через 17 секунд
-=ЮрА=-, ща

@-=ЮрА=- · 02.05.2013, 17:40

Учитывать будем сложность возведения в степень логорифмирование - вызов данных функций довольно ресурсозатратная штука, мы накинем по формулам, в итоге сравним мой пробор до N/20 и твой код.

Ternsip · 02.05.2013, 18:05

-=ЮрА=-, вот

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 <iostream>
#include <algorithm>
#include <map>
#include <string>
 
using namespace std;
 
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;
}
 
bool simple (long long a){
    int j;
    for(j = 2; j * j <= a && a % j; ++j);
    return (j * j > a && a - 1);
}
 
bool test(long long c){
    if (c < 99990001)
        return simple(c);
    return MillerRabin(c, 19);
}
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    long long n;
    cin >> n;
    for (int i = 0; i < 1000; i++) {
        if (test(n))
            puts("ok");
    }
    return 0; 
}

Добавлено через 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
 
using namespace std;
 
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;
}
 
bool simple (long long a){
    if (a < 2)
        return false;
    if (a == 2)
        return true;
    int j;
    for(j = 3; j * j <= a && a % j; j+=2);
    return (j * j > a && a - 1);
}
 
bool test(long long c){
    if (c <= 999900010)
        return simple(c);
    return MillerRabin(c, 19);
}
 
int main(){
    long long n;
    cin >> n;
    if (test(n))
       puts("ok");
    return 0; 
}

Добавлено через 4 минуты
-=ЮрА=-, вот ещё доработал

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
#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;
}
 
// 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 long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) return true;
        if((b >> i) & 1) d = (long 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 long c){
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main(){
    long long n;
    cin >> n;
    if (test(n))
            puts("ok");
    return 0; 
}

Добавлено через 1 минуту
-=ЮрА=-, если придумаете алгоритм много быстрее, то может удостоитесь награды и похвалы выше чем сам http://ru.wikipedia.org/wiki/%... 1%80%D0%B8

Добавлено через 3 минуты
-=ЮрА=-, и, естественно, что решетом Эратосфена, блочным и другими нельзя пользоваться, это читы

@NaikoN · 02.05.2013, 18:11 **[ТС]**

-=ЮрА=-,Ternsip, Молодцы, я бы такое не написал

Ternsip · 02.05.2013, 18:19

PS прекальк "преподсчётом" тоже нельзя пользоваться.

Добавлено через 2 минуты
-=ЮрА=-, ну и на всякий случай, если у меня прога всё же будет лагать, хоть я и сомневаюсь, то в return MillerRabin(c, 19); поставьте 10 вместо 19

@isaak · 02.05.2013, 18:31

Ternsip у вашей первой программы при запуске выскакивает ошибка.

@-=ЮрА=- · 02.05.2013, 18:50

Ternsip, скриншоты и коды подсчёта операций прилагаю, если что то захочешь обсудить по +1 на операцию не вопрос.

Вобщем так у меня вышло почти в 3 раза эффективней (55 к операций против 190 к у тебя), причём я думаю тут не арифметическая а геометрическая зависимость в числе операций. О понятности кода моего и твоего говорить тоже не буду. Остаётся добавить что в нолике твой алгоритм вылетает.

Мой код из поста 19

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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(int num);
double OPCount = 0;
 
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
//      else
//          continue;
//      if( nCount && nCount % 80 == 0 )
//          system("pause");
    }
    cout<<"Total count of operations : "<<OPCount<<endl;
    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;
}

Твой код из поста 26 (я взял последний т.к ты указал что он самый последний и доработанный)

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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
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 += 1;
        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(2, 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()
{
    int nCount  = 0;
    for(int num = 1; num <= 3571; num++)
    {
        if(test(num))
            cout<<(nCount++)<<" - "<<num<<endl;
     //   else
       //     continue;
      //  if( nCount && nCount % 80 == 0 )
        //    system("pause");
    }
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}

Ternsip · 02.05.2013, 18:55

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

Добавлено через 1 минуту
-=ЮрА=-, и использовал самую быструю проверку числа на простоту, известную кому-либо на данный момент. Кроме, конечно, решета Эратосфена.

@-=ЮрА=- · 02.05.2013, 18:55

Не по теме:

-=ЮрА=-, если придумаете алгоритм много быстрее, то может удостоитесь награды и похвалы выше чем сам

- быстрее на многоядерной машине я могу распараллелить так что ты и глазом не моргнёшь а ПК выведет большую часть известного числового ряда. Если придумаете...я уже вон выше привёл в 3 раза эффективней причём код написал сидя смотря мульт и играя с дочерью, а не обложившись справочниками и прочей атрибутикой, пффф...

Ternsip · 02.05.2013, 18:57

-=ЮрА=-, вы написали очень не эффективный код, вы тестировали алгоритмы на маленьких числах, попробуйте на числах больше миллиарда.

@-=ЮрА=- · 02.05.2013, 19:03

Ternsip, хорош!Возьми да посмотри на цифры. И в нуле поправь свой "супер"код.

Добавлено через 55 секунд

Не по теме:

Хотя миллиард говоришь, ну хорошо...

Добавлено через 4 минуты
Ternsip, especially for you (ну не миллиард а 100 млн, простишь меня ладно?)
Юзни код мєйна
У меня

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    int nCount  = 0;
/*  for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
//      else
//          continue;
//      if( nCount && nCount % 80 == 0 )
//          system("pause");
    }*/
    isSimple(100000000);
    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
int main()
{
    int nCount  = 0;
   /* for(int num = 1; num <= 3571; num++)
    {
        if(test(num))
            cout<<(nCount++)<<" - "<<num<<endl;
     //   else
       //     continue;
      //  if( nCount && nCount % 80 == 0 )
        //    system("pause");
    }*/
    test(100000000);
 
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}

И погляди результат 82 операции у тебя и 2 у меня.

Ternsip · 02.05.2013, 19:06

https://www.cyberforum.ru/atta... 1367507123
https://www.cyberforum.ru/atta... 1367507123
https://www.cyberforum.ru/atta... 1367507123

Ternsip · 02.05.2013, 19:06

-=ЮрА=-, 100000000 разделится сразу на двойку, я вам говорю попробуйте тест 9999999900000001

@-=ЮрА=- · 02.05.2013, 19:09

Ternsip, у меня стоит тип инт у которого есть предел INT_MAX, а ты тулишь числа превосходящие его. (Даю подсказку замени int num на long long num, а то не догадаешся до этого видимо)
Я поставил isSimple(899999999); и получил 14 операций у себя и test(899999999); - 84 на твоём коде, это всё экстраполируется и на большие числа

Ternsip · 02.05.2013, 19:10

-=ЮрА=-, какую же вы ерунду пишете

посмотрите 1-й скриншот.

@-=ЮрА=- · 02.05.2013, 19:15

Всё вот тебе код и умолкни наконец

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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    isSimple(9999999900000001);
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long 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;
    }
    num /= 10;
    for(i = 9 + 2; i <= num / 10 && bSimple; i += 2)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}

Ternsip · 02.05.2013, 19:17

-=ЮрА=-, только 9999999900000001 простое число, а у вас программа скажет, что оно составное

isSimple вернёт false

@-=ЮрА=- · 02.05.2013, 22:46

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

-=ЮрА=-, только 9999999900000001 простое число, а у вас программа скажет, что оно составное isSimple вернёт false

- да ты что(научись компилить лучше

), я тебе уже писал что присваивать 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
#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; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
        else
            continue;
        if( nCount && nCount % 80 == 0 )
            system("pause");
    }
    cout<<"Total count of operations : "<<OPCount<<endl;
    if(isSimple(9999999900000001))
        cout<<"IS SIMPLE"<<endl;
    if(isSimple(2147483647))
        cout<<"IS SIMPLE"<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long 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 <= 100 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}

https://ideone.com/XaVpci

497 - 3547
498 - 3557
499 - 3559
500 - 3571
Total count of operations : 39337
IS SIMPLE
IS SIMPLE

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

Не по теме:

В любом случае алгоритм представленный мной обладает производительностью на порядок выше того что ты пытаешся представить как панацею, вдобавок у тебя не работает нолик. Про длинну и понятность кода я молчу...

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 17:25
	-=ЮрА=-, теперь согласен. хоть это и не самое оптимальное решение. 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 17:35
	-=ЮрА=-, оооо, спасибо) тогда проверьте отдельно для числа 9999999900000001 на тесте Миллера Рабина, котый я в начале привёл Добавлено через 17 секунд -=ЮрА=-, ща 0

@-=ЮрА=- 6614 / 4256 / 401 Регистрация: 08.08.2009 Сообщений: 10,325 Записей в блоге: 24
	02.05.2013, 17:40
	Учитывать будем сложность возведения в степень логорифмирование - вызов данных функций довольно ресурсозатратная штука, мы накинем по формулам, в итоге сравним мой пробор до N/20 и твой код. 0

@NaikoN 2 / 2 / 1 Регистрация: 01.05.2013 Сообщений: 109
	02.05.2013, 18:11 [ТС]
	-=ЮрА=-,Ternsip, Молодцы, я бы такое не написал 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 18:19
	PS прекальк "преподсчётом" тоже нельзя пользоваться. Добавлено через 2 минуты -=ЮрА=-, ну и на всякий случай, если у меня прога всё же будет лагать, хоть я и сомневаюсь, то в return MillerRabin(c, 19); поставьте 10 вместо 19 0

@isaak 90 / 125 / 28 Регистрация: 17.10.2010 Сообщений: 1,333
	02.05.2013, 18:31
	Ternsip у вашей первой программы при запуске выскакивает ошибка. 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 18:55
	-=ЮрА=-, я не знаю что вы тут вообще сделали, но вы засеките время на тесте n = 9999999900000001 моего решения и вашего и не нужно ничего вставлять в мой код. Добавлено через 1 минуту -=ЮрА=-, и использовал самую быструю проверку числа на простоту, известную кому-либо на данный момент. Кроме, конечно, решета Эратосфена. 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 18:57
	-=ЮрА=-, вы написали очень не эффективный код, вы тестировали алгоритмы на маленьких числах, попробуйте на числах больше миллиарда. 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 19:06
	https://www.cyberforum.ru/atta... 1367507123 https://www.cyberforum.ru/atta... 1367507123 https://www.cyberforum.ru/atta... 1367507123 Миниатюры 0

@-=ЮрА=- 6614 / 4256 / 401 Регистрация: 08.08.2009 Сообщений: 10,325 Записей в блоге: 24
	02.05.2013, 19:09
	Ternsip, у меня стоит тип инт у которого есть предел INT_MAX, а ты тулишь числа превосходящие его. (Даю подсказку замени int num на long long num, а то не догадаешся до этого видимо) Я поставил isSimple(899999999); и получил 14 операций у себя и test(899999999); - 84 на твоём коде, это всё экстраполируется и на большие числа 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 19:10
	-=ЮрА=-, какую же вы ерунду пишете посмотрите 1-й скриншот. 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	02.05.2013, 19:17
	-=ЮрА=-, только 9999999900000001 простое число, а у вас программа скажет, что оно составное isSimple вернёт false 1