сито до 2 миллиардов дает ошибку сегментации - PullRequest
Новая
       84

сито до 2 миллиардов дает ошибку сегментации

1 голос
/ 21 ноября 2019

Я использую эту программу, чтобы проверить число, простое или нет.

Использовать алгоритм - Сито: 

#include<bits/stdc++.h>
//#define _max    2000000001
#define _max    20000001
using namespace std;
bool sieve[_max];
void init()
{
    memset(sieve,true,sizeof(sieve));
    sieve[0]=sieve[1]=false;
    for(int i=2;i<_max;i+=2)
    {
        sieve[i]=false;
    }
}
void go_sieve(int n)
{
    n++;
    for(int i=3;i<n;i+=2)
    {
        if(sieve[i]==false)
            continue;
        for(int j=2*i;j<n;j+=i)
            sieve[j]=false;
    }
}
void print(int n)
{
    n++;
    printf("-------------\n");
    for(int i=0;i<n;i++)
    {
        if(sieve[i])
            cout << i << " ";
    }
    printf("\n-------------\n");
}
int main()
{
    init();
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        go_sieve(x);
        //print(x);
        if(sieve[x])
            printf("Prime\n");
        else
            printf("Not prime\n");
    }
    return 0;
}

Теперь оно работает до 2e7 и довольно плавно, но яхотите проверить до 2e9, если я изменю свой _max на 2000000001, он выдаст мне segmentation error и выйдет с кодом ошибки.

Как я могу решить эту проблему?

Я попробовал новый подход с набором: 

#include<bits/stdc++.h>
//#define _max    200001
//#define _max    20000001
#define _max    2000000001
using namespace std;
set<int>prime;
set<int>nprime;
void init()
{
    prime.insert(2);
}
void go_sieve()
{
    for(int i=3;i<_max;i+=2)
    {
        if(prime.find(i)==prime.end() && nprime.find(i)==nprime.end())
        {
            prime.insert(i);
            //cout << i << endl;
            for(int j=2*i;j<_max;j+=i)
                nprime.insert(j);
        }
        if(nprime.find(i)!=nprime.end())
            nprime.erase(nprime.find(i));
    }
}
void print()
{
    set<int> ::iterator itt;
    printf("-------------\n");
    for(itt=prime.begin();itt!=prime.end();itt++)
    {
        cout << *itt << " ";
    }
    printf("\n-------------\n");
}
int main()
{
    init();
    go_sieve();
    //print();
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        if(prime.find(x)!=prime.end())
            printf("Prime\n");
        else
            printf("Not prime\n");
    }
    return 0;
}

Цель - выполнить его в пределах 512 МБ ~ 1 ГБ памяти.

Ответы [ 2 ]

0 голосов
/ 21 ноября 2019

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

Однако вам не нужен такой большой массив. Используя Сито Эратосфена, вам нужно рассчитать числа до x. Вместо массива вы можете использовать std::vector и увеличивать его размер при вычислении большего числа чисел. Это должно позволить вам вычислить некоторые числа, но с большими числами вы снова достигнете предела памяти.

Вы также можете использовать некоторый алгоритм, который требует от вас хранить меньше чисел. Чтобы определить, является ли x простым, вам нужно только сравнить с простыми числами, которые меньше квадратного корня из x. Вам не нужно хранить числа, которые не являются простыми числами. С x = 1e10 вам нужно будет хранить только 5e8 чисел .

Вот пример с вектором (возможно, не оптимальным): 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

std::vector<int> primes = {2};

void calculate(int x) {
    const int largest_prime = primes.back();
    if (largest_prime >= x) {
        // Already calculated
        return; 
    }
    for (size_t i = largest_prime + 1; i <= x; i++) {
        bool not_prime = false;
        for (size_t j = 0; j < primes.size(); j++) {
            if (i % primes[j] == 0) {
                not_prime = true;
                break;
            }
        }
        if (!not_prime) {
            primes.push_back(i);
        }
    }
}

bool check(int x) {
    calculate(x);
    return std::find(primes.begin(), primes.end(), x) != primes.end();
}

int main() {
    std::cout << check(15) << std::endl;
    std::cout << check(256699) << std::endl;
}
0 голосов
/ 21 ноября 2019

Я не могу воспроизвести это на моей системе. Я предполагаю, что это связано с системно-зависимым ограничением.

Вы объявляете sieve как глобальный массив (статическая продолжительность хранения), и он огромен (то есть 2000000001 * sizeof (bool) - может быть 2-8G в зависимости от размера bool). Возможно, ваша система не справится с этим.

Вместо глобального массива попробуйте использовать динамическое распределение: 

// bool sieve[_max]; comment out this
bool* sieve = NULL;

...
...

int main()
{
    sieve = (bool*)malloc(_max * sizeof *sieve);
    if (sieve == NULL)
    {
        // out of memory
        exit(1);
    }

    ...

При этом:

Ваш код на C ++, но вашстиль больше похож на C.

В C ++ вы, вероятно, вместо этого будете использовать std::vector. Это сделало бы все намного проще.

Кстати: также избегайте глобальных. Вместо этого определите вектор (или динамический массив) в main и передайте его по ссылке в функции.

...