Sigsegv 在范围内寻找质数时出错

Question

在解决在给定范围内寻找素数的问题时，我遇到了 Sigsegv 错误，我无法找到我的错误在哪里以及如何更正它

#include<iostream>
#include<cmath>
using namespace std;
int primes[10000000];// stores prime upto a max value
int prime[10000000];//stores prime in a given range
int main()
{
  long long int t,m,n,s,k,q;
  for(long long int i=1;i<=1000000;i++){
      primes[i]=1;
      primes[1]=0;
  }

    //stores prime using sieve    
    for(long long int i=2;i<=sqrt(1000000);i++) 
    {
        if(primes[i]==1)
        {
            for(long long int j=2;i*j<=1000000;j++)
            {
                primes[i*j]=0;
            }
        }   
    }
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        //marking all indices as 1 
        for(long long int i=m;i<=n;i++)      
        {
          prime[i]=1;
        }
        //calculating which offset to mark
        for(long long int i=2;i<=n-m+1;i++)       
        {
            if(primes[i]==1)
            {
                long long int x=(m/i)*i;
                while(x<m)
                x=x+i;   
                for(long long int j=x;j<=n;j=j+i)
                {
                    if(primes[j]==0)
                    prime[j]=0;
               }  
             }
           }         
        for(long long int i=m;i<=n;i++)
        {
            if(prime[i]==1&&i!=1)
            cout<<i<<"\n";
        }
    }
    return 0;
}

Answer 1

您使用的编译器可能不允许静态分配大块数据，例如

int primes[10000000];

这超过了 2^25 个字节。如此大的块可能会超出编译器或其在 SPOJ 上的运行时的能力。 new 或 malloc() 这么大的块可能是可能的，但这种解决方法可能会让你走入死胡同。

另一个问题是您从输入中读取 m 和 n 而未验证它们是否在安全范围内。 SPOJ 上的至少一个测试用例 比您的代码限制 高出两个数量级，因为您的分配是 10^7，但 SPOJ 限制是 10^9。这意味着崩溃是不可避免的。

您不需要完整的 32 位整数来保存布尔值；您可以使用 bool 从而将内存需求减少到四分之一。或者，您可以将每个字节大小的数组单元视为一个 8 位的打包位图，与现在相比，将内存使用减少到 1/32。由于您使用的是 C++，所有内容都已经以 std::vector<bool> 的形式为您整齐地打包（在后台进行位打包）。

注意：要筛选所有不超过 PRIME1 限制 1,000,000,000 的数字，数组必须大一百倍。尽管可以筛选该范围内的所有数字（时间限制非常慷慨 - 大约是此任务所需时间的 10000 倍），但对于完全不熟悉编程的人来说，这可能并不容易。

但是，该任务并不要求筛选十亿个数字。它只要求筛选一小部分范围，每个范围不超过 100001 个数字。即使是简单的、未优化的代码也可以在一毫秒内完成，即使 std::vector<bool> 比任何合理的数据结构都慢一个数量级。

要注意的关键字是 'windowed Sieve of Eratosthenes'。这里和 Code Review 上有数百个主题涉及 PRIME1。看一看。

Answer 2

考虑一个案例：

1
100000000 100000009

当我运行你在 ideone 上的代码 link: here。

It gave Run-time Error.

原因： 你已经初始化了大小为 10⁷ 的素数数组但是m, n 的运行ge 最多可以达到 10⁹.

因此，一旦遇到prime[i]=1，你的系统就崩溃了。

for(long long int i=m;i<=n;i++)      
{
      prime[i]=1;
}

建议：学习埃拉托色尼筛法。由于 m, n 的运行ge 可以是
1 <= m <= n <= 1000000000, n-m<=100000

如果我们取 10⁹ 的平方根，那么它将接近 31622。所以，这就是为什么我们选择了一个大小为 32000 （在我的代码中） 的数组 num 的原因。之后，我们计算出位于2 - 32000.

的运行ge中的素数个数

现在，考虑三种情况：

当m and n都小于32000，那么就简单的使用计算出来的prime数组，打印需要的质数。
当m and n都在32000的运行ge之外时，则检查i(在运行ge of m and n) not 可被任何质数 整除（出现在代码中的 prime 数组中）。如果 i 不能被 整除，则打印它。
如果m and n的运行ge部分小于32000，部分在32000之外，则将运行ge分成两部分，其中一部分完全小于等于 32000，另一个完全大于 32000。对第一个运行ge 重复步骤 1，对第二个运行ge 重复步骤 2。

下面是我的代码，请觉得有用，但不要复制粘贴到 SPOJ 上。

#include<stdio.h>
#include<math.h>

int num[32000] = {0},prime[3500],prime_index = -1;

int main() {
    prime[++prime_index] = 2;
    int i,j,k;

    for(i=3;    i<179;     i += 2) {
        if(num[i] == 0) {
            prime[++prime_index] = i;

            for(j = i*i, k = 2*i;    j<=32000;   j += k) {
                num[j] = 1;
            }
        }
    }

    for(;   i<=32000;   i+= 2) {
        if(num[i] == 0) {
            prime[++prime_index] = i;
        }
    }

    int t,m,n;
    scanf("%i",&t);
    while(t--) {
        scanf("%i%i",&m,&n);

        if(m == 1)
            m++;

        if(m == 2 && m <= n) {
            printf("2\n");
        }

        int sqt = sqrt(n) + 1, arr[100005] = {0};

        for(i=0;    i<=prime_index; i++) {
            if(prime[i] > sqt) {
                sqt = i;
                break;
            }
        }

        for(;   m<=n && m <= prime[prime_index];   m++) {
            if(m&1 && num[m] == 0) {
                printf("%i\n",m);
            }
        }

        for(i=0;    i<=sqt;     i++) {
            j = prime[i] * (m / prime[i]);

            if(j < m) {
                j += prime[i];
            }

            for(k=j;    k<=n;   k += prime[i]) {
                arr[k-m] = 1;
            }
        }

        for(i=0;    i<=n-m; i++) {
            if(!arr[i]) {
                printf("%i\n",m+i);
            }
        }

        printf("\n");
    }
    return 0;
}

欢迎大家提出疑问。

Sigsegv 在范围内寻找质数时出错

Sigsegv Error in finding prime in a range

c++

primes

sieve

sieve-of-eratosthenes