Сито Эратосфена не работает за пределами 200 000 - PullRequest
Новая
       8

Сито Эратосфена не работает за пределами 200 000

0 голосов
/ 13 ноября 2018

Моя программа на C ++ для вычисления всех простых чисел с использованием метода сита Эратосфена останавливается после 200 000. Но мне нужно вычислить простые числа до 2 миллионов. Буду признателен за помощь, если кто-то может сказать мне, где я ошибся с моим кодом. 

#include <iostream>
#include<math.h>
using namespace std;

void isprime(long long int prime[],long int n)
{
    for(long long int i=0;i<=n;i++)
    {
        prime[i]=1;
    }
    prime[0]=prime[1]=0;
    for(long long int i=2;i<=sqrt(n);i++)
    {
        if(prime[i]==1)
        {
            for(long long int j=2;i*j<=n;j++)
                prime[i*j]=0;
        }
    }
    for(long long int i=0;i<=n;i++)
    {
        if(prime[i]==1)
        cout<<i<<endl;
     }
}
int main()
{
    long long int n;
    cout<<"enter number";
    cin>>n;
    long long int prime[n+1];
    isprime(prime,n);
    return 0;
}

1 Ответ

0 голосов
/ 15 ноября 2018

Поскольку каждый элемент сита содержит только 0 или 1, нет необходимости использовать long long int для хранения каждого элемента.std::vector<bool> потенциально использует 1 бит на элемент и, таким образом, является оптимальным для эффективности памяти.

Вот ваш код с очень небольшим количеством модификаций для использования std::vector<bool>.Поскольку для получения и установки отдельных элементов требуется некоторая битовая манипуляция, эта версия может быть медленнее, чем код, который использует один байт или элемент int для каждого элемента sieve.Вы можете сравнить различные версии и выбрать подходящий компромисс для своих нужд. 

#include <cmath>
#include <cstddef>
#include <exception>
#include <iostream>
#include <string>
#include <vector>


// returns the number of primes <= n
long isprime(long n) {
    std::vector<bool> prime(n + 1);
    for (long i = 0; i <= n; i++) {
        prime[i] = 1;
    }
    prime[0] = prime[1] = 0;
    long upper_bound = std::sqrt(n);
    for (long i = 2; i <= upper_bound; i++) {
        if (prime[i] == 1) {
            for (long j = 2; i * j <= n; j++)
                prime[i * j] = 0;
        }
    }
    long num_primes = 0;
    for (long i = 0; i <= n; i++) {
        if (prime[i] == 1) {
            ++num_primes;
//          std::cout << i << std::endl;
        }
    }
    return num_primes;
}

int main() {
    std::cout << "Enter the sieve size: ";
    std::string line;
    std::getline(std::cin, line);
    std::cout << std::endl;
    long len = std::stol(line);
    long num_primes = isprime(len);
    std::cout << "There are " << num_primes << " primes <= " << len << std::endl;
    return 0;
}
...