Сито реализации Эратосфена

Question

Сито реализации Эратосфена

Я пытаюсь реализовать алгоритм для Sieve of Eratosthenes, но я не знаю, почему эта программа падает для больших программ. Первоначально я использовал vector но сейчас я реализую это с помощью динамического выделения памяти.

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;

unsigned isqrt(unsigned value) {
return static_cast<unsigned>(sqrt(static_cast<float>(value)));
}

int main()
{
int t;
cin >> t;
long long * N;
long long * M;
long long n, m;
N = new long long[t];
M = new long long[t];
for(int i = 0; i < t ; i++){
cin >> M[i] >> N[i];
}

for(int i = 0; i < t ; i++){
n = N[i];
m = M[i];

bool * A;
A = new bool[n];
if(A == 0)
{
cout << "Memory cannot be allocated";
return 0;
}

for(int i=0;i < n;i++){
A[i]=true;
}
A[0] = false;
A[1] = false;

unsigned sqrt = isqrt(n);
for(int i = 2; i <= sqrt; i++)
{
if(A[i] == true){
for(int j = i*i; j <= n; j = j + i)
{
A[j] = false;
}
}
}

for(int i = m;i < n;i++)
{
if(A[i] == true )
cout << i << "\n";
}

delete[] A;
}

delete[] M;
delete[] N;
return 0;
}

Программа вылетает при больших значениях n а также m (~ 10 ^ 16). Пожалуйста, помогите мне.

0

c++sieve-of-eratosthenes

Решение

Другие решения

Если вы собираетесь написать сито Эратосфена на C ++, как насчет того, использование C ++, не пытайтесь воспринимать это как какое-то безумие между C и ассемблером.

#include <vector>
#include <iostream>

unsigned long primes = 0;

int main() {
int number = 10000000;
std::vector<bool> sieve(number,false);
sieve[0] = sieve[1] = true;

for(int i = 2; i<number; i++) {
if(!sieve[i]) {
++primes;
for (int temp = 2*i; temp<number; temp += i)
sieve[temp] = true;
}
}
std::cout << "found: " << primes << " Primes\n";
return 0;
}

2

Если n достаточно велико, чтобы вызвать ошибку выделения памяти, программа вылетит из-за неправильной обработки ошибок выделения памяти здесь

 A = new bool[n];
if(A == 0)
{
cout << "Memory cannot be allocated";
return 0;
}

new не возвращает 0 в случае ошибки, но выдает std :: bad_alloc, который не перехватывается, что, в свою очередь, приведет к неожиданному (), завершению () и, наконец, вызову abort ().
Правильная версия будет:

  try
{
A = new bool[n];
}
catch (std::bad_alloc& ba)
{
std::cerr << "Memory cannot be allocated: " << ba.what() << '\n';
}

1

Запустите это в отладчике, чтобы определить, где происходит сбой, и отладьте оттуда. Скорее всего, это будет очевидно в этой точке.

Вы можете сделать это либо из IDE, либо из командной строки. В последнем случае скомпилируйте с -g и запустить в такой программе, как gdb, Google что-то вроде «GDB Cheatsheet», чтобы начать.

-1

Источник

Accepted Answer

for(int j = i*i; j <= n; j = j + i)
^^

Если j == n затем A[j] = false назначит элемент после конца массива. Тест должен быть j < n,

4