Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
#1

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

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

Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 1 и на само себя, сложное число-которое делится на 1 и на само себя и на какое-то еще число, 5 -простое число, 10-сложное число.
P.S. Вот программа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
 int simple (int x,int i=1)
{
    int fn;
    for(i=1;i<=x;i++)
    {
        if(i!=1||i!=x)
        {
            if(!(x%i))
            {
                fn=0;
                return fn;
            }
        }
    }
    fn=1;
    return fn;
}
int main()
{
    //ifstream cin("input.txt");
    long int x,i=1;
    cin>>x;
    if(simple(x,i)==0)
    {
        cout<<"composite";
        return 0;
    }
    if(simple(x,i)==1)
    {
        cout<<"prime";
            return 0;
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2013, 11:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Эффективный алгоритм поиска простых чисел на С++ (C++):

функция поиска простых чисел - C++
не могу сделать функции для поиска простых чисел, вот код функции int prost(int x) { if (x/2) return true; else ...

Программа поиска простых чисел - C++
Необходимо написать программу для поиска простых чесил в интервале от 1 до 100 на языке СИ.Простое число — это натуральное число, имеющее...

Функция для поиска ближайших простых чисел - C++
Ув. товарищи программисты , нужна помощь. Требуется функция с помощью которой можно найти 2 ближайших ПРОСТЫХ числа к веденному числу. ...

Почему программа поиска простых чисел работает только до 61? - C++
Добрый день, Помогите, пожалуйста, разобраться. Программа для поиска простых чисел. На экран отображает только простые числа до 61, ...

Алгоритм нахождения простых чисел - C++
Не могу найти в интернете нормальный код алгоритма нахождения простых чисел. Помогите пожалуйста. Добавлено через 2 минуты ...

Алгоритм нахождения простых чисел - C++
Вопросы: 1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 104 операций за...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:50 #16
-=ЮрА=-, мне жалко вас расстраивать, но, увы, снова не верно, 221 = 17 * 13
-=ЮрА=-
02.05.2013, 16:51
  #17

Не по теме:

NaikoN, хорошо я основательно подумаю, чтобы код остался в пределах строк 30-35

Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:56 #18
-=ЮрА=-, 247 = 13*19

Добавлено через 30 секунд
-=ЮрА=-, да вот я уже 2 отличия привёл

Добавлено через 20 секунд
-=ЮрА=-, 169 221 247 289 299 323 361 377 391 403 437 481 493 527 529 533 551 559 589 611 629 667 689 697 703 713 731 767 779 793 799 817 841 851 871 вот отличия

Добавлено через 3 минуты
-=ЮрА=-, нужно проверять не до константы а до корня числа
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 17:19 #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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(int num);
 
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
    }
    return 0;
}
 
bool isSimple(int num)
{
    int i;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= num / 10 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}

Не по теме:

ЗЫ:

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

Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 17:23 #20
Кому захочется проверять поштучно - модифицируем мэйн вот так
C++
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
        if( nCount && nCount % 40 == 0 )
            system("pause");
    }
    return 0;
}
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 17:25 #21
-=ЮрА=-, теперь согласен. хоть это и не самое оптимальное решение.
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 17:33 #22
Это чтоб проскакивать нормально по 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
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 17:35 #23
-=ЮрА=-, оооо, спасибо)
тогда проверьте отдельно для числа 9999999900000001
на тесте Миллера Рабина, котый я в начале привёл

Добавлено через 17 секунд
-=ЮрА=-, ща
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 17:40 #24
Учитывать будем сложность возведения в степень логорифмирование - вызов данных функций довольно ресурсозатратная штука, мы накинем по формулам, в итоге сравним мой пробор до N/20 и твой код.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 18:05 #25
-=ЮрА=-, вот
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/%D0%9C%...B0%D1%80%D0%B8

Добавлено через 3 минуты
-=ЮрА=-, и, естественно, что решетом Эратосфена, блочным и другими нельзя пользоваться, это читы
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 18:11  [ТС] #26
-=ЮрА=-,Ternsip, Молодцы, я бы такое не написал
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 18:19 #27
PS прекальк "преподсчётом" тоже нельзя пользоваться.

Добавлено через 2 минуты
-=ЮрА=-, ну и на всякий случай, если у меня прога всё же будет лагать, хоть я и сомневаюсь, то в return MillerRabin(c, 19); поставьте 10 вместо 19
isaak
102 / 39 / 9
Регистрация: 17.10.2010
Сообщений: 658
02.05.2013, 18:31 #28
Ternsip у вашей первой программы при запуске выскакивает ошибка.
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 18:50 #29
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
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 18:55 #30
-=ЮрА=-, я не знаю что вы тут вообще сделали, но вы засеките время на тесте n = 9999999900000001 моего решения и вашего
и не нужно ничего вставлять в мой код.

Добавлено через 1 минуту
-=ЮрА=-, и использовал самую быструю проверку числа на простоту, известную кому-либо на данный момент. Кроме, конечно, решета Эратосфена.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2013, 18:55
Привет! Вот еще темы с ответами:

Алгоритм отбора простых чисел - C++
Сижу учу С++ по Шилтду (Базовый курс) И вот папался такой алгоритм, на котором меня просто заклинило на 2 часа, так и не смог...

Алгоритм нахождения простых чисел - C++
Не так давно начал изучать с++. Вот попытался написать программу которая вычисляет простое ли число которые вы ввели в консоль? но она...

Алгоритм нахождения ПРОСТЫХ чисел в файле - C++
Заполнить файл f целыми числами, полученными с помощью генератора случайных чисел. Из файла f получить файл g, оставив только ПРОСТЫЕ...

Найти наименьшее из четырех чисел используя алгоритм поиска наибольшего из двух чисел - C++
Найти наименьшее из четырех чисел используя алгоритм поиска наибольшего из двух чисел.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.05.2013, 18:55
Ответ Создать тему
Опции темы

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