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

@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 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

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,338
	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