Eratosthenes实施筛 [英] Sieve of Eratosthenes implementation

问题描述

我正在尝试为Eratosthenes筛分算法实现算法，但我不知道为什么该程序会因大型程序而崩溃。最初我使用的是 vector ，但现在我使用动态内存分配来实现它。

I am trying to implement algorithm for Sieve of Eratosthenes but I don't know why this program crashes for larger programs. Initially I was using vector but now I am implementing this using dynamic memory allocation.

#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较大的值，程序崩溃code>和 m （〜10 ^ 16）。

The program crashes for larger values of n and m (~10^16). Kindly help me out.

推荐答案

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

如果 j == n ，然后 A [j] = false 将分配给数组末尾的元素。测试应为 j< n 。

If j == n then A[j] = false will assign to an element past the end of the array. The test should be j < n.

这篇关于Eratosthenes实施筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！