时间戳

首页 > 解决方案 > SIGSEGV 背后的推理？

c++ - SIGSEGV 背后的推理？

问题描述

我正在尝试解决 SPOJ 上的“Prime Generator”问题。最初，我使用了埃拉托色尼筛法，但这需要很长时间。因此，我实施了分段筛。我的代码在我的机器上运行良好，但是当我将它提交给 SPOJ 时，我收到消息“运行时错误 (SIGSEGV)”。

谷歌搜索告诉我 SIGSEGV 与无效的内存引用或使用过多的内存有关。我是竞争性编程的新手，看不到我哪里出错了。

如果有帮助，我正在使用 CPP14-CLANG 语言。

这是代码：

#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
#include <sstream>

int main(){
    int nt=0, l_value=0, r_value=0, v=1;
    int lr_array[20] = {0};
    std::vector <int> soe;
    std::vector <std::string> token;
    std::vector <int> prime_list(1e5, 1);

    //take number of test cases and their respective range
    std::cin>>nt;
    std::cin.ignore();

    for(int i=0;i<nt;i++)
    {
        std::string line;
        getline(std::cin, line);
        std::stringstream check1(line);
        std::string intermediate;
        while(getline(check1, intermediate, ' '))
        {
            token.push_back(intermediate);
        }

        for(int i=0;i<token.size();i++)
        {
            lr_array[i] = std::stoi(token[i]);
        }

    }


    //Find out primes till sqrt(y) by using Sieve of Erathosthenes
    for(int i=0;i<=32000;i++)
    {
        soe.push_back(1);
    }

    for(int k=2;k<32000;k++)
    {
        if(soe[k])
        {

            for(int j=(k*k);j<=32000;j+=k)
            {
                soe[j] = 0;
            }
        }
    }

    //Use each element from SoE list to determine non-primes in given range

    for(int i=0;i<nt;i++)
    {
        for(int j=2;j<soe.size();j++)
        {
            if(soe[j] && (j<=lr_array[i+v]))
            {
                int temp = int((lr_array[2*i]/j));
                temp = temp*j;
                if(temp<lr_array[2*i]){
                    temp += j;
                }

                for(int k=lr_array[2*i];k<=lr_array[i+v];k++)
                {
                    if(k==lr_array[2*i])
                        {
                            if(j==2){prime_list[temp]=0;continue;}
                            else{temp+=j;prime_list[temp]=0;continue;}

                        }
                    if(temp<=lr_array[i+v])
                    {
                        prime_list[temp]=0;
                        temp += j;
                    }
                    else{
                        break;
                    }

                }
            }

        }

        if(lr_array[2*i]<=2){prime_list[2]=1;}

        for(int l=lr_array[2*i];l<=lr_array[i+v];l++){
            if(prime_list[l]==1)
            {
                std::cout<<l<<std::endl;
            }

    }
        v++;
        std::cout<<std::endl;       
    }
    return 0;
}

我也提到了这个StackOverflow 问题，但它没有帮助。

标签： c++runtime-errorc++14

解决方案

当代码尝试访问未分配的内存部分时，会发生分段错误。如果你不够幸运，你可能会发现你的代码执行得“很好”。那就是发生内存损坏的时候。该进程写入一块已通过更改分配但不属于感兴趣的数组的内存块。

在您的内部循环中，您尝试访问soe的内存远远超过分配的内存。它落在外面（如果你幸运的话）或破坏其他变量（如果你不走运）

for(int k=2;k<32000;k++)
{
    if(soe[k])
    {

        for(int j=(k*k);j<=32000;j+=k)
        // j grows up to 32000. Largesr valid index for soe is 31999
        {
            soe[j] = 0; // <====== This is where segfault happens
        }
    }
}

推荐阅读