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

@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 минуты

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .	сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .
Теория всего 12. ВГК на планете в стратегической игре "терра" anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .	Теория всего 10. Клод трусишка anaschu 21.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