0

我正在尝试为埃拉托色尼筛法实现算法，但我不知道为什么该程序会因较大的程序而崩溃。最初我正在使用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)的较大值而崩溃。请帮帮我。

4

4 回答 4

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

如果j == nthenA[j] = false将分配给数组末尾之后的元素。测试应该是j < n。

于 2013-04-12T20:51:57.553 回答
2

如果您打算用 C++ 编写 Eratosthenes 筛选器，那么如果您实际使用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;
}
于 2013-04-12T21:44:14.983 回答
1

如果 n 大到足以导致内存分配错误，程序将由于此处不正确的内存分配错误处理而崩溃

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

new 不会在错误时返回 0，但会抛出没有被捕获的 std::bad_alloc，这反过来会导致意外（）然后终止（），最后中止（）被调用。
正确的版本是：

  try
  {
    A = new bool[n];
  }
  catch (std::bad_alloc& ba)
  {
    std::cerr << "Memory cannot be allocated: " << ba.what() << '\n';
  }
于 2013-04-12T21:06:19.003 回答
-1

在调试器中运行它以确定崩溃的位置并从那里进行调试。那时很可能会很明显。

您可以从 IDE 或命令行执行此操作。在后一种情况下-g，使用诸如gdb. 谷歌诸如“gdb cheatsheet”之类的东西来开始。

于 2013-04-12T20:57:11.930 回答